New algorithms on wavelet trees and applications to information retrieval
From MaRDI portal
Publication:418727
DOI10.1016/j.tcs.2011.12.002zbMath1243.68161arXiv1011.4532MaRDI QIDQ418727
Gonzalo Navarro, Travis Gagie, Simon J. Puglisi
Publication date: 30 May 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1011.4532
68W05: Nonnumerical algorithms
68P05: Data structures
68P20: Information storage and retrieval of data
Related Items
Spaces, Trees, and Colors, A Succinct Solution to Rmap Alignment, Practical Compact Indexes for Top-kDocument Retrieval, Bidirectional Variable-Order de Bruijn Graphs, Computing all-vs-all MEMs in run-length-encoded collections of HiFi reads, Fast construction of wavelet trees, Compact binary relation representations with rich functionality, Colored range queries and document retrieval, Space-efficient data-analysis queries on grids, Compact and succinct data structures for multidimensional orthogonal range searching, Wheeler graphs: a framework for BWT-based data structures, New space/time tradeoffs for top-\(k\) document retrieval on sequences, Lempel-Ziv compressed structures for document retrieval, Top-\(k\) term-proximity in succinct space, Range selection and predecessor queries in data aware space and time, Wavelet trees for all, Document listing on repetitive collections with guaranteed performance, Edge minimization in de Bruijn graphs, General Document Retrieval in Compact Space, Indexes for Document Retrieval with Relevance, Efficient Construction of a Compressed de Bruijn Graph for Pan-Genome Analysis, Compact Indexes for Flexible Top-$$k$$ Retrieval, Time-Optimal Top-$k$ Document Retrieval, Space-Efficient Frameworks for Top- k String Retrieval
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Towards optimal range medians
- Indexing text using the Ziv--Lempel trie
- Succinct data structures for flexible text retrieval systems
- Range mode and range median queries in constant time and sub-quadratic space
- Time bounds for selection
- Compressed representations of sequences and full-text indexes
- Suffix Arrays: A New Method for On-Line String Searches
- Self-indexed Text Compression Using Straight-Line Programs
- Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
- Space-Efficient Algorithms for Document Retrieval
- Finding Patterns in Given Intervals
- Position-Restricted Substring Searching
- Range Medians
- Indexing compressed text
- Rank/select operations on large alphabets
- Top-k Ranked Document Search in General Text Databases
- Range Non-overlapping Indexing and Successive List Indexing
- A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
- Towards Optimal Range Medians
- Data Structures for Range Median Queries
- A Functional Approach to Data Structures and Its Use in Multidimensional Searching
- Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
- Alternation and redundancy analysis of the intersection problem
- Practical Entropy-Compressed Rank/Select Dictionary
- Intersection in Integer Inverted Indices
- Combinatorial Pattern Matching
- Efficient Data Structures for the Orthogonal Range Successor Problem
- COMPRESSED REPRESENTATIONS OF PERMUTATIONS, AND APPLICATIONS
- String Processing and Information Retrieval
- An experimental investigation of set intersection algorithms for text searching
- Improved Bounds for Range Mode and Range Median Queries
- Transposition invariant string matching
- STACS 2005