2013/07/25 by Gonzalo Navarro, Yakov Nekrich, Navarro, Gonzalo +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Data Storage Technologies #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Retrieval (cs.IR)
paper · pdf · doi:10.48550/arxiv.1307.6789
openalex publication_date 2013/07/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let D be a collection of D documents, which are strings over an alphabet of size σ, of total length n. We describe a data structure that uses linear space and and reports k most relevant documents that contain a query pattern P, which is a string of length p, in time O(p/logσn+k), which is optimal in the RAM model in the general case where \lg D = Θ(log n), and involves a novel RAM-optimal suffix tree search. Our construction supports an ample set of important relevance measures... [clip] When \lg D = o(log n), we show how to reduce the space of the data structure from O(nlog n) to O(n(logσ+log D+loglog n)) bits... [clip] We also consider the dynamic scenario, where documents can be inserted and deleted from the collection. We obtain linear space and query time O(p(loglog n)2/logσn+log n + kloglog k), whereas insertions and deletions require O(log1+ε n) time per symbol, for any constant ε>0. Finally, we consider an extended static scenario where an extra parameter par(P,d) is defined, and the query must retrieve only documents d such that par(P,d)∈ [τ1,τ2], where this range is specified at query time. We solve these queries using linear space and O(p/logσn + log1+ε n + klogεn) time, for any constant ε>0. Our technique is to translate these top-k problems into multidimensional geometric search problems. As an additional bonus, we describe some improvements to those problems.