Document listing on repetitive collections with guaranteed performance

DOI10.1016/j.tcs.2018.11.022zbMath1422.68062arXiv1707.06374OpenAlexW2964108621WikidataQ128847431 ScholiaQ128847431MaRDI QIDQ2632016

Gonzalo Navarro

Publication date: 17 May 2019

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Related Items (3)

Sensitivity of string compressors and repetitiveness measures ⋮ Random access in persistent strings and segment selection ⋮ Unnamed Item

Uses Software

• Wumpus
• PATRICIA
• r-index

Cites Work

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

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