2012/11/22 by Roberto Konow, Gonzalo Navarro, Konow, Roberto +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Image and Video Retrieval Techniques #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.1211.5353
openalex publication_date 2012/11/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An optimal index solving top-k document retrieval [Navarro and Nekrich, SODA12] takes O(m + k) time for a pattern of length m, but its space is at least 80n bytes for a collection of n symbols. We reduce it to 1.5n to 3n bytes, with O(m+(k+log log n) log log n) time, on typical texts. The index is up to 25 times faster than the best previous compressed solutions, and requires at most 5% more space in practice (and in some cases as little as one half). Apart from replacing classical by compressed data structures, our main idea is to replace suffix tree sampling by frequency thresholding to achieve compression.