Time-Optimal Top-$k$ Document Retrieval
From MaRDI portal
Publication:2963583
DOI10.1137/140998949zbMath1359.68053arXiv1307.6789OpenAlexW2587741488MaRDI QIDQ2963583
Yakov Nekrich, Gonzalo Navarro
Publication date: 15 February 2017
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1307.6789
Related Items (10)
String indexing for top-\(k\) close consecutive occurrences ⋮ Space-efficient data-analysis queries on grids ⋮ Top-\(k\) document retrieval in optimal space ⋮ Ranked Document Retrieval in External Memory ⋮ Gapped indexing for consecutive occurrences ⋮ Path queries on functions ⋮ Fast compressed self-indexes with deterministic linear-time construction ⋮ Indexing weighted sequences: neat and efficient ⋮ Ranked document selection ⋮ Fast Compressed Self-Indexes with Deterministic Linear-Time Construction
Cites Work
- Colored range queries and document retrieval
- Space-efficient data-analysis queries on grids
- 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
- The design of dynamic data structures
- Succinct data structures for flexible text retrieval systems
- Worst-case optimal insertion and deletion methods for decomposable searching problems
- Dynamic dictionary matching
- Improved dynamic dictionary matching
- On-line construction of suffix trees
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- New space/time tradeoffs for top-\(k\) document retrieval on sequences
- Improved compressed indexes for full-text document retrieval
- Compressed suffix trees with full functionality
- Rank and select revisited and extended
- General Document Retrieval in Compact Space
- Top-k Document Retrieval in External Memory
- Towards an Optimal Space-and-Query-Time Index for Top-k Document Retrieval
- Alphabet-Dependent String Searching with Wexponential Search Trees
- Compressed representations of sequences and full-text indexes
- Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
- Alphabet-Independent Compressed Text Indexing
- Fully compressed suffix trees
- Space-Efficient Frameworks for Top- k String Retrieval
- Space-Efficient Algorithms for Document Retrieval
- Constructing Efficient Dictionaries in Close to Sorting Time
- Dynamic ordered sets with exponential search trees
- Top-k Ranked Document Search in General Text Databases
- Fast Prefix Search in Little Space, with Applications
- A LINEAR SPACE DATA STRUCTURE FOR ORTHOGONAL RANGE REPORTING AND EMPTINESS QUERIES
- Online Sorted Range Reporting
- Priority Search Trees
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- A Space-Economical Suffix Tree Construction Algorithm
- Algorithms on Strings, Trees and Sequences
- A Generalized Suffix Tree and Its (Un)Expected Asymptotic Behaviors
- Optimal External Memory Interval Management
- Jewels of Stringology
- A Functional Approach to Data Structures and Its Use in Multidimensional Searching
- A SIMPLE BALANCED SEARCH TREE WITH O(1) WORST-CASE UPDATE TIME
- Persistence, randomization and parallelization: On some combinatorial games and their applications (abstract)
- On Hardness of Several String Indexing Problems
- Space-Efficient Framework for Top-k String Retrieval Problems
- Spaces, Trees, and Colors
- Improved Single-Term Top-k Document Retrieval
- Dynamic LCA Queries on Trees
- Orthogonal range searching on the RAM, revisited
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- Integer priority queues with decrease key in constant time and the single source shortest paths problem
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Time-Optimal Top-$k$ Document Retrieval
