Document Retrieval on Repetitive Collections
Travis Gagie, Aleksi Hartikainen, Kalle Karhu, Juha Kärkkäinen,
Gonzalo Navarro, Simon J. Puglisi, and Jouni Sirén
Most of the fastest-growing string collections today are repetitive, that is,
most of the constituent documents are similar to many others. As these
collections keep growing, a key approach to handling them is to exploit their
repetitiveness, which can reduce their space usage by orders of magnitude.
We study the problem of indexing repetitive string collections in order to
perform
efficient document retrieval operations on them. Document retrieval problems
are routinely solved by search engines on large natural language collections,
but the techniques are less developed on generic string collections. The case
of repetitive string collections is even less understood, and there are very
few existing
solutions. We develop two novel ideas, interleaved LCPs and
precomputed document lists, that yield highly compressed indexes solving
the problem of document listing (find all the documents where a string
appears), top-k document retrieval (find the k documents where a string
appears most often), and document counting (count the number of documents
where a string appears). We also show that a classical data structure
supporting the latter query becomes highly compressible on repetitive data.
Finally, we show how the tools we developed can be combined to solve ranked
conjunctive and disjunctive multi-term queries under the simple tf-idf model
of relevance. We thoroughly evaluate the resulting techniques in various
real-life repetitiveness scenarios, and recommend the best choices for
each case.