Dekel Tsur

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| 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) or 2|CSA|+ω(1).