Top-k document retrieval in optimal space

• We present an index for top-k most frequent document retrieval whose space is |CSA|+o(n)+DlognD+O(D) bits.
• The space complexity is better than previous results for the problem.
• The index is based on an index of Belazzougui and Navarro.

We present an index for top-k most frequent document retrieval whose space is |CSA|+o(n)+DlognD+O(D) bits, and its query time is O(logklog2+ϵn) per reported document, where D is the number of documents, n   is the sum of lengths of the documents, and |CSA||CSA| is the space of the compressed suffix array for the documents. This improves over previous results for this problem, whose space complexities are |CSA|+ω(n)|CSA|+ω(n) or 2|CSA|+ω(1)2|CSA|+ω(1).