Gmail doesn't even have substring search (e.g. searching for "hack" will not find instances of "hacker"). I think that would be a prerequisite for Instant-style searching.
True. But it's worth noting that those predictions are sufficient for a slow, partially-working substring search. Gmail could search for the n most likely completions of your query terms in addition to the normal search, and collate the results.
Comments
Gmail doesn't even have substring search (e.g. searching for "hack" will not find instances of "hacker"). I think that would be a prerequisite for Instant-style searching.
No it wouldn't, instant search doesn't search substrings, but strings it thinks you are about to type in.
You could create a lookup table of those for each GMail account in the background even if you didn't have substring search.
True. But it's worth noting that those predictions are sufficient for a slow, partially-working substring search. Gmail could search for the n most likely completions of your query terms in addition to the normal search, and collate the results.