the 'locate' command is faster than everything but arguably not as convenient (being a commandline tool). It seems to support non-ntfs (meaning it doesn't support ntfs) linux filesystems.
edit: catfish is a gui front-end available for locate.
edit: catfish is a gui front-end available for locate.