Towards an Optimal Space-and-Query-Time Index for Top-k Document Retrieval

Abstract

Let $\D = $$\{d_1,d_2,...d_D\}$ be a given set of $D$ string documents of total length $n$, our task is to index $\D$, such that the $k$ most relevant documents for an online query pattern $P$ of length $p$ can be retrieved efficiently. We propose an index of size $|CSA|+n\log D(2+o(1))$ bits and $O(t_s(p)+k\log \log n+poly\log \log n)$ query time for the basic relevance metric \emph{term-frequency}, where $|CSA|$ is the size (in bits) of a compressed full text index of $\D$, with $O(t_s(p))$ time for searching a pattern of length $p$ . We further reduce the space to $|CSA|+n\log D(1+o(1))$ bits, however the query time will be $O(t_s(p)+k(\log \sigma \log \log n{)}^{1+\epsilon }+poly\log \log n)$, where $\sigma$ is the alphabet size and $\epsilon >0$ is any constant.

12 pages

Cited by in corpus (1)

• Practical Top-K Document Retrieval in Reduced Space