Space-Efficient Frameworks for Top- k String Retrieval
From MaRDI portal
Publication:3189644
DOI10.1145/2590774zbMath1295.68230OpenAlexW2040254860MaRDI QIDQ3189644
Rahul Shah, Sharma V. Thankachan, Wing-Kai Hon, Jeffrey Scott Vitter
Publication date: 12 September 2014
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2590774
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Information storage and retrieval of data (68P20) Algorithms on strings (68W32)
Related Items (17)
Top-\(k\) term-proximity in succinct space ⋮ Document retrieval with one wildcard ⋮ Space-efficient indexes for forbidden extension queries ⋮ Unnamed Item ⋮ String indexing for top-\(k\) close consecutive occurrences ⋮ Ranked Document Retrieval with Forbidden Pattern ⋮ Compact Indexes for Flexible Top-$$k$$ Retrieval ⋮ Faster repetition-aware compressed suffix trees based on block trees ⋮ Ranked Document Retrieval in External Memory ⋮ Time-Optimal Top-$k$ Document Retrieval ⋮ Gapped indexing for consecutive occurrences ⋮ A framework for designing space-efficient dictionaries for parameterized and order-preserving matching ⋮ Succinct indexes for reporting discriminating and generic words ⋮ Lempel-Ziv compressed structures for document retrieval ⋮ Ranked document retrieval for multiple patterns ⋮ Ranked document selection ⋮ On hardness of several string indexing problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Top-\(k\) document retrieval in optimal space
- New algorithms on wavelet trees and applications to information retrieval
- Efficient index for retrieving top-\(k\) most frequent documents
- Fast set intersection and two-patterns matching
- Succinct data structures for flexible text retrieval systems
- Time bounds for selection
- Log-logarithmic worst-case range queries are possible in space theta(N)
- Faster compressed dictionary matching
- Geometric BWT: compressed text indexing via sparse suffixes and range searching
- An optimal algorithm for selection in a min-heap
- On position restricted substring searching in succinct space
- Improved compressed indexes for full-text document retrieval
- Compressed suffix trees with full functionality
- Space Efficient Suffix Trees
- Low Redundancy in Static Dictionaries with Constant Query Time
- Indexes for Document Retrieval with Relevance
- Top-k Document Retrieval in External Memory
- Top-k Document Retrieval in Compact Space and Near-Optimal Time
- Algorithms and Data Structures for External Memory
- Towards an Optimal Space-and-Query-Time Index for Top-k Document Retrieval
- Document Listing for Queries with Excluded Pattern
- Sorted Range Reporting
- Compressed representations of sequences and full-text indexes
- Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
- Suffix Arrays: A New Method for On-Line String Searches
- Cache-Oblivious Algorithms
- Indexing compressed text
- Dictionary matching and indexing with errors and don't cares
- Rank/select operations on large alphabets
- Top-k Ranked Document Search in General Text Databases
- A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
- A Space-Economical Suffix Tree Construction Algorithm
- Fast Pattern Matching in Strings
- A Fast Merging Algorithm
- 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
- Document Listing on Repetitive Collections
- Space-Efficient Framework for Top-k String Retrieval Problems
- Spaces, Trees, and Colors
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
This page was built for publication: Space-Efficient Frameworks for Top- k String Retrieval
