Space-efficient frameworks for top-k string retrieval
From MaRDI portal
Publication:3189644
DOI10.1145/2590774zbMATH Open1295.68230OpenAlexW2040254860MaRDI QIDQ3189644FDOQ3189644
Authors: Wing-Kai Hon, Rahul Shah, Sharma V. Thankachan, 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
Recommendations
- New space/time tradeoffs for top-\(k\) document retrieval on sequences
- Towards an optimal space-and-query-time index for top-\(k\) document retrieval
- Top-\(k\) document retrieval in compact space and near-optimal time
- Improved single-term top-\(k\) document retrieval
- Top-\(k\) document retrieval in optimal time and linear space
Information storage and retrieval of data (68P20) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)
Cites Work
- A Fast Merging Algorithm
- Improved compressed indexes for full-text document retrieval
- Algorithms and data structures for external memory
- Compressed representations of sequences and full-text indexes
- Cache-oblivious algorithms
- Indexing compressed text
- Dictionary matching and indexing with errors and don't cares
- Title not available (Why is that?)
- Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
- Title not available (Why is that?)
- Title not available (Why is that?)
- Space-Efficient Framework for Top-k String Retrieval Problems
- Top-\(K\) color queries for document retrieval
- Fully-functional succinct trees
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- Compressed suffix trees with full functionality
- Space-efficient preprocessing schemes for range minimum queries on static arrays
- Log-logarithmic worst-case range queries are possible in space theta(N)
- Indexes for document retrieval with relevance
- Top-\(k\) document retrieval in external memory
- Document listing for queries with excluded pattern
- Suffix Arrays: A New Method for On-Line String Searches
- A Space-Economical Suffix Tree Construction Algorithm
- Fast Pattern Matching in Strings
- Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences
- Fast set intersection and two-patterns matching
- Succinct data structures for flexible text retrieval systems
- Geometric BWT: compressed text indexing via sparse suffixes and range searching
- Sorted range reporting
- Rank/select operations on large alphabets
- 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
- Time bounds for selection
- Space efficient suffix trees
- A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
- Low redundancy in static dictionaries with constant query time
- Faster compressed dictionary matching
- Towards an optimal space-and-query-time index for top-\(k\) document retrieval
- Top-\(k\) ranked document search in general text databases
- Top-\(k\) document retrieval in compact space and near-optimal time
- Top-\(k\) document retrieval in optimal space
- Efficient index for retrieving top-\(k\) most frequent documents
- An optimal algorithm for selection in a min-heap
- Document listing on repetitive collections
- Title not available (Why is that?)
- On position restricted substring searching in succinct space
Cited In (19)
- Succinct oblivious RAM
- A framework for designing space-efficient dictionaries for parameterized and order-preserving matching
- Compact indexes for flexible top-\(k\)
- Faster repetition-aware compressed suffix trees based on block trees
- On hardness of several string indexing problems
- Document retrieval with one wildcard
- Time-optimal top-\(k\) document retrieval
- Ranked Document Retrieval in External Memory
- Space-efficient indexes for forbidden extension queries
- Ranked document retrieval with forbidden pattern
- Ranked document retrieval for multiple patterns
- String indexing for top-\(k\) close consecutive occurrences
- Lempel-Ziv compressed structures for document retrieval
- Ranked document selection
- Indexes for document retrieval with relevance
- Top-\(k\) term-proximity in succinct space
- Faster repetition-aware compressed suffix trees based on block trees
- Gapped indexing for consecutive occurrences
- Succinct indexes for reporting discriminating and generic words
This page was built for publication: Space-efficient frameworks for top-\(k\) string retrieval
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3189644)
