When I last looked for a Linux replacement for it, none had the real time updates or the instant search ui, and even those that claimed to index the file system for a quick search were very slow. I actually ended up writing my own hacky and rudimentary GUI over locate to achieve something that fits my needs (and of course doesn't support real time updates).
Maybe things changed since then? Any chance that the HN crowd knows of a good Linux replacement for Everything?