Practical Compact Indexes for Top-k Document Retrieval

摘要

We present a fast and compact index for top-k document retrieval on general string collections, in which givenrna string pattern, the index returns the k documents where it appearsmost often.We adapt a linear-space andrnoptimal-time theoretical solution, whose implementation poses various algorithm engineering challenges.rnAlthough a naive implementation of the optimal solution is estimated to require around 80n bytes for a textrncollection of n symbols, our implementation requires 2.5n to 3.0n bytes, text included, and answers queriesrnwithin microseconds. This outperforms all previous practical indexes by orders of magnitude; the only indexrnusing less space is hundreds of times slower. Our index can be built on collections of hundreds of gigabytesrnand on tokenized text collections.