New algorithms on wavelet trees and applications to information retrieval
From MaRDI portal
Publication:418727
DOI10.1016/j.tcs.2011.12.002zbMath1243.68161arXiv1011.4532OpenAlexW2151453116MaRDI 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
Nonnumerical algorithms (68W05) Data structures (68P05) Information storage and retrieval of data (68P20)
Related Items (25)
Top-\(k\) term-proximity in succinct space ⋮ Fast construction of wavelet trees ⋮ Document listing on repetitive collections with guaranteed performance ⋮ Bidirectional Variable-Order de Bruijn Graphs ⋮ Space-Efficient Frameworks for Top- k String Retrieval ⋮ Range selection and predecessor queries in data aware space and time ⋮ Wheeler graphs: a framework for BWT-based data structures ⋮ Efficient Construction of a Compressed de Bruijn Graph for Pan-Genome Analysis ⋮ Compact Indexes for Flexible Top-$$k$$ Retrieval ⋮ Compact binary relation representations with rich functionality ⋮ Colored range queries and document retrieval ⋮ Space-efficient data-analysis queries on grids ⋮ Edge minimization in de Bruijn graphs ⋮ Computing all-vs-all MEMs in run-length-encoded collections of HiFi reads ⋮ Computing longest Lyndon subsequences and longest common Lyndon subsequences ⋮ Time-Optimal Top-$k$ Document Retrieval ⋮ Wavelet trees for all ⋮ Spaces, Trees, and Colors ⋮ New space/time tradeoffs for top-\(k\) document retrieval on sequences ⋮ Lempel-Ziv compressed structures for document retrieval ⋮ A Succinct Solution to Rmap Alignment ⋮ General Document Retrieval in Compact Space ⋮ Compact and succinct data structures for multidimensional orthogonal range searching ⋮ Indexes for Document Retrieval with Relevance ⋮ Practical Compact Indexes for Top-kDocument 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
This page was built for publication: New algorithms on wavelet trees and applications to information retrieval
