4
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 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

0

Reset to default

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.