I've been playing with doing file change detection based on NTFS journals. There are some caveats, but it looks very promising. It's O(1) basically instead of O(file-size).