###
Faster Top-*k* Document Retrieval in Optimal Space

####
Gonzalo Navarro and Sharma Thankachan

We consider the problem of retrieving the *k* documents from a collection of
strings where a given pattern *P* appears most often. We show that, by
representing the collection using a Compressed Suffix Array
*CSA*, a data structure using the asymptotically optimal
*|CSA|+o(n)* bits can answer queries in the time needed by
*CSA* to find
the suffix array interval of
the pattern plus *O(k lg^2 k lg^e n)* accesses to suffix array cells,
for any constant *e>0*. This is *lg n / lg k* times faster than the
only previous solution using optimal space, *lg k* times slower than the
fastest structure
that uses twice the space, and *lg^2 k lg^e n* times the lower-bound
cost of obtaining *k* document identifiers from the CSA. To obtain the
result we introduce a tool called the *sampled document array*, which
can be of independent interest.