Navigating multiple inversed indexes

or the story about creating custom PhraseQuery for Lucene with black-jack non-strict number of search terms

Lucene is possibly the most known open-source full-text search engine. Having worked with it quite a lot I am very surprised that it lacks the function for efficient searching of phrases with non-strict number of terms.


Suppose you are searching for some phrase and want to see the results even if some terms in your query are not presented in the results (but those documents that have all the terms in the correct order are still on the top).
I.e. you are searching for "homes in new york with swimming pools" and still expecting to see the results with "homes in new york with pools" | "homes in new york with rooftop pools".
The standard Lucene's class to deal with phrase queries - PhraseQuery. It does the amazing thing with calculating and scoring the "slope" of your terms in the text but searches for all terms in your query. One can accomlish original task by constructing a massive tree-structure of subqueries but it will work very slowly and the code will look pretty bad and is certainly not the way to go for a performance maniac like me.

Here I present my own approach to solve this task. It can be viewed as a generalization algorithm for Lucene's PhraseQuery.

Abstracting out of Lucene this task can be described as follows:
You have a system of inverted indexes for each term(word) in you query. The inverted index in a nutchell is a list of document|row ids or pointers to docs|rows that contain the specific term|word. So this structure is designed to answer the question "which documents contain this word?". Usually such indexes are augmented with some 'fast navigation to desired document id' function. The most obvious implementation that supports this function efficiently is skip-list. Lucene has two main types of inverted indexes - TermDocs and TermPositions. The first one describes documents and frequences of a term in each document and the second class contains also the term's positions.

The simple pseudo-code for our index is:

Index {

    doc(): returns current docId

    nextDoc() : returns next docId

    scrollTo(docId)

}

So we have a set of such indexes (each per query word|term).



The main task is to find all docs which have at least m out of n possible words
For example, if m=3 then documents 4 and 12 (see pic.) should be in the results set.
If m=2 documents 2, 7, 9 should also be presented.


Scrolling an index usually possible only in the forward direction to save index space in memory (in this case it only needs the forward pointers for skip list).

This dictates the natural way of processing indexes - scroll one of them and check the current doc id of all indexes. Assume the maximum current document Id for indexes is M and minimum is m and if we increment the index with min docId and its next doc value m2 appears to be m2>M then we can be sure that there are no docs with ids<m2 that contain all the terms and we can scroll the other indexes up to m2.

Employing these facts it is possible to work out the following algorithm:

1. Move all the indexes to the first position and sort them according to docIds in ascending order

2. If the number of indexes is less than m stop the process.

3. Check the docId of the first index and the m-th index in the list.

4. If they are equal we have a match of at least m terms for doc=doc_1. We can process this result further - check if there are more than m matches and calculate the slope of terms inside the text. Suppose we have m2 matches (m<=m2<=n). Now, after the slope processing, we can increment these m2 indexes to their next docs and sort the list.

5. Otherwise doc_1<doc_m (indexes are sorted). Scroll index 1 up to doc_m as there are no new results for docId<doc_m.

6. The new doc_1>=doc_m or null when an index runs out of docs. If new doc_1 is not null insert the first index in the list of indexes in order to keep it sorted. There is only need to check for doc_1>doc_i where i>m. One can employ binary search or simple sequential iteration to scan the m-th to N tail of the index list. Usually the number of search terms is small so the simple one-by-one check would be enough.

7. If the first index runs out of docs - remove it from the index list.

8. Go to step 2.

Suppose we are searching for at least m=2 tokens in the query "word1 word2 word3" for indexes shown on the pic above. Suppose that 25, 13, 12 are the last docIds for those three indexes.

Introduce the notion of index state in the list - (i, d) - index for i-th word has current pointer to the doc=d.

Then the algorithm steps are:
The index list is (1,1) (2,2) (3,2).
Check doc_1 & doc_m=doc_2 : 1<2. Scroll index1 up to doc_2=2. The new value for the first index is 4.
So we have the index list : (1,4) (2,2) (3,2)
Insert (1,4) to the appopriate position to keep the list sorted:
  (2,2) (3,2) (1,4) - we have a match doc_1=doc_m=doc_2=2;

The further list states and matches are:
  (2,2) (3,2) (1,4)  results: [2]; increment (2,2) (3,2) and sort the list
  (2,4) (3,4) (1,4)  results: [2,4];  incrementall and sort
  (2,5) (1,7) (3,7) results: [2,4]; scroll (2,5) to doc=7 & insert in the new position
  (1,7) (3,7) (2,9) results: [2,4,7];
  (1,8) (3,9) (2,9) results: [2,4,7]; scroll (1,8) to doc=9
  (3,9) (2,9) (1,12) results: [2,4,7,9];
  (3,10) (2,12) (1,12) results: [2,4,7,9];   scroll (3,10) to doc=12
  (2,12) (1,12) (3,12) results: [2,4,7,9,12];
  (2,13) (1,20) results: [2,4,7,9,12];   scroll (2,13) to doc=20
  (1,20) results: [2,4,7,9,12]; STOP



I hope the idea of algorithm is clear now and one can use it to write his own implementation of PhraseQuery with an ability to specify the minimum number of matching terms and a custom strategy for scoring matches with different number of containing terms.