How Lucene positional index works so efficiently?

user_15643716 0
Viewed 188

Usually any search engine software creates inverted indexes to make searches faster. The basic format is:-

word: <docnum ,positions>, <docnum ,positions>, <docnum ,positions> .....

Whenever there is a search query inside quote like "Harry Potter Movies" it means there should be exact match of positions of word and in searches like within k word queries like hello /4 world it generally means that find the word world in the range of 4 word distance either in left or right from the word hello. My question is that we can employ solution like linearly checking the postings and calculating distances of words like in query, but if collection is really large we can't really search all the postings. So is there any other data structure or kind of optimisation lucene or solr uses?

One first solution can be only searching some k postings for each word. Other solution can be only searching top docs(usually called champion list sorted by tf-idf or similar during indexing), but more better docs can be ignored. Both solutions have some disadvantage, they both don't ensure quality. But in Solr server we get assured quality of results even in large collections. How?

inverted-index information-retrieval solr lucene python
1 Answers

The phrase query you are asking about here is actually really efficient to compute the positions of, because you're asking for the documents where 'Harry' AND 'Potter' AND 'Movies' occur.

Lucene is pretty smart, but the core of its algorithm for this is that it only needs to visit the positions lists of documents where all three of these terms even occur.

Lucene's postings are also sharded into multiple files: Inside the counts-files are: (Document, TF, PositionsAddr)+ Inside the positions-files are: (PositionsArray)

So it can sweep across the (doc, tf, pos_addr) for each of these three terms, and only consult the PositionsArray when all three words occur in the specific document. Phrase queries have the opportunity to be really quick, because you only visit at most all the documents from the least-frequent term.

If you want to see a phrase query run slowly (and do lots of disk seeks!), try: "to be or not to be" ... here the AND part doesn't help much because all the terms are very common.

user_10570480
Related