New space/time tradeoffs for top-k document retrieval on sequences

We address the problem of indexing a collection D={T1,T2,…,TD}D={T1,T2,…,TD} of D string documents of total length n, so that we can efficiently answer top-k queries: retrieve k documents most relevant to a pattern P of length p   given at query time. There exist linear-space data structures, that is, using O(n)O(n) words, that answer such queries in optimal O(p+k)O(p+k) time for an ample set of notions of relevance. However, using linear space is not sufficiently good for large text collections. In this paper we explore how far the space/time tradeoff for this problem can be pushed. We obtain three results: (1) When relevance is measured as term frequency (number of times P   appears in a document TiTi), an index occupying |CSA|+o(n)|CSA|+o(n) bits answers the query in time O(tsearch(p)+klg2klgεn), where CSACSA is a compressed suffix array indexing DD, tsearch(p)tsearch(p) is its time to find the suffix array interval of P  , and ε>0ε>0 is any constant. (2) With the same measure of relevance, an index occupying |CSA|+nlgD+o(nlgσ+nlgD) bits answers the query in time O(tsearch(p)+klg⁎k), where lg⁎k is the iterated logarithm of k  . (3) When the relevance depends only on the documents, an index occupying |CSA|+O(nlglgn) bits answers the query in O(tsearch(p)+ktSA) time, where tSAtSA is the time the CSACSA needs to retrieve a suffix array cell. On our way, we obtain some other results of independent interest.