Googling "large horse walks into house" also returns results that contain "large horse in a house" and "the house has large horses".

How is Google able to return near-matches and not just direct matches?

What are the methods that search engines use to perform such queries so quickly?

I know about phrase search and proximity search and how they can be implemented using a positional inverted index, but this is neither a phrase search (because the terms don't have to be directly adjacent nor in order) nor proximity search (because the terms don't have to be in order nor within a fixed width of each other — nor all present)

It seems like somehow these search engines are doing a string edit distance lookup across billions of documents in fractions of a second.

How have they managed to implement this kind of searching on top of an index?

  • 1
    $\begingroup$ I think the answer to this question is a textbook. For your own research, you may try and find out how tools like ElasticSearch work. Most likely, in practice, the correct answer is a combination of clever distributed algorithms/data structures, selectively applied AI/ML techniques, and raw processing power. $\endgroup$
    – Raphael
    Feb 6, 2022 at 16:51


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.