Document listing on repetitive collections with guaranteed performance

DOI10.1016/J.TCS.2018.11.022zbMATH Open1422.68062arXiv1707.06374OpenAlexW2964108621WikidataQ128847431 ScholiaQ128847431MaRDI QIDQ2632016FDOQ2632016

Authors: Gonzalo Navarro 

Publication date: 17 May 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: We consider document listing on string collections, that is, finding in which strings a given pattern appears. In particular, we focus on repetitive collections: a collection of size $N$ over alphabet $[1,sigma]$ is composed of $D$ copies of a string of size $n$, and $s$ edits are applied on ranges of copies. We introduce the first document listing index with size $ildeO(n+s)$, precisely $O((nlogsigma+slo{g}^{2}N)logD)$ bits, and with useful worst-case time guarantees: Given a pattern of length $m$, the index reports the $doc>0$ strings where it appears in time $O(mlo{g}^{1+epsilon}Ncdotdoc)$, for any constant $epsilon>0$ (and tells in time $O(mlogN)$ if $doc=0$). Our technique is to augment a range data structure that is commonly used on grammar-based indexes, so that instead of retrieving all the pattern occurrences, it computes useful summaries on them. We show that the idea has independent interest: we introduce the first grammar-based index that, on a text $T[1,N]$ with a grammar of size $r$, uses $O(rlogN)$ bits and counts the number of occurrences of a pattern $P[1,m]$ in time $O(m^2+mlo{g}^{2+epsilon}r)$, for any constant $epsilon>0$. We also give the first index using $O(zlog(N/z)logN)$ bits, where $T$ is parsed by Lempel-Ziv into $z$ phrases, counting occurrences in time $O(mlo{g}^{2+epsilon}N)$.

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

Recommendations

• Document Listing on Repetitive Collections with Guaranteed Performance
• Document listing on repetitive collections
• Document retrieval on repetitive collections
• Flexible indexing of repetitive collections
• Indexing highly repetitive collections
• scientific article; zbMATH DE number 2119724
• Publication:4886029

zbMATH Keywords

succinct data structuresrange minimum queriesrange countinggrammar compressionrepetitive string collectionsdocument listinggrammar-based indexing

Mathematics Subject Classification ID

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

Cites Work

• Information retrieval. Implementing and evaluating search engines.
• Title not available (Why is that?)
• Elements of Information Theory
• A fully linear-time approximation algorithm for grammar-based compression
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Title not available (Why is that?)
• Space-Efficient Framework for Top-k String Retrieval Problems
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Efficient randomized pattern-matching algorithms
• Alphabet-Independent Compressed Text Indexing
• Practical Entropy-Compressed Rank/Select Dictionary
• On the Complexity of Finite Sequences
• Spaces, Trees, and Colors
• Succinct data structures for flexible text retrieval systems
• Wavelet trees for all
• Fast relative Lempel-Ziv self-index for similar sequences
• Suffix Tree of Alignment: An Efficient Index for Similar Data
• Indexing Highly Repetitive Collections
• Indexing similar DNA sequences
• On compressing and indexing repetitive sequences
• Space-efficient data-analysis queries on grids
• New algorithms on wavelet trees and applications to information retrieval
• Title not available (Why is that?)
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• The Smallest Grammar Problem
• Algorithms for approximate string matching
• Approximation of grammar-based compression via recompression
• A \textit{really} simple approximation of smallest grammar
• Self-Indexed Grammar-Based Compression
• LRM-trees: compressed indices, adaptive sorting, and compressed permutations
• Document Listing on Repetitive Collections
• A Faster Grammar-Based Self-index
• Composite Repetition-Aware Data Structures
• Fully Dynamic Data Structure for LCE Queries in Compressed Space
• Random Access to Grammar-Compressed Strings and Trees
• LZ77-Based Self-indexing with Faster Pattern Matching
• Universal compressed text indexing
• Compressed indexing with signature grammars
• The smallest grammar problem revisited
• Time-space trade-offs for Lempel-Ziv compressed indexing
• Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings

Cited In (5)

• Contextual Pattern Matching
• Document Listing on Repetitive Collections with Guaranteed Performance
• Title not available (Why is that?)
• Sensitivity of string compressors and repetitiveness measures
• Random access in persistent strings and segment selection

Uses Software

• Wumpus
• PATRICIA
• r-index

This page was built for publication: Document listing on repetitive collections with guaranteed performance

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