Towards an optimal space-and-query-time index for top-k document retrieval

DOI10.1007/978-3-642-31265-6_14zbMATH Open1358.68092arXiv1108.0554OpenAlexW1504477191MaRDI QIDQ2904490FDOQ2904490

Authors: Wing-Kai Hon, Rahul Shah, Sharma V. Thankachan 

Publication date: 14 August 2012

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Abstract: Let $D=$$d_1,d_2,\mathrm{...}{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|+nlogD(2+o(1))$ bits and $O(t_s(p)+kloglogn+polyloglogn)$ 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|+nlogD(1+o(1))$ bits, however the query time will be $O(t_s(p)+k(logsigmaloglogn{)}^{1+epsilon}+polyloglogn)$, where $sigma$ is the alphabet size and $epsilon>0$ is any constant.

Full work available at URL: https://arxiv.org/abs/1108.0554

Recommendations

• Top-\(k\) document retrieval in compact space and near-optimal time
• New space/time tradeoffs for top-\(k\) document retrieval on sequences
• Top-\(k\) document retrieval in optimal space
• Top-\(k\) document retrieval in optimal time and linear space
• Time-optimal top-\(k\) document retrieval

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Algorithms on strings (68W32)

Cited In (17)

• Top-\(k\) document retrieval in optimal space
• Space-time trade-offs for some ranking and searching queries
• Colored range queries and document retrieval
• Efficient index for retrieving top-\(k\) most frequent documents
• Time-optimal top-\(k\) document retrieval
• The quantile index -- succinct self-index for top-\(k\) document retrieval
• Top-\(k\) document retrieval in compact space and near-optimal time
• Practical compact indexes for top-\(k\) document retrieval
• Array range queries
• New space/time tradeoffs for top-\(k\) document retrieval on sequences
• Top-\(k\) document retrieval in optimal time and linear space
• Improved single-term top-\(k\) document retrieval
• Indexes for document retrieval with relevance
• Top-\(k\) document retrieval in external memory
• Space-efficient frameworks for top-\(k\) string retrieval
• Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences
• General document retrieval in compact space

This page was built for publication: Towards an optimal space-and-query-time index for top-\(k\) document retrieval

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2904490)