Spaces, Trees, and Colors
From MaRDI portal
Publication:5176183
DOI10.1145/2535933zbMath1305.68078arXiv1304.6023OpenAlexW2068471245MaRDI QIDQ5176183
Publication date: 2 March 2015
Published in: ACM Computing Surveys (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1304.6023
information retrievalstring searchingtext indexingcompact data structurescolored range queriesorthogonal range searches
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Data structures (68P05) Information storage and retrieval of data (68P20) Algorithms on strings (68W32)
Related Items
Top-\(k\) term-proximity in succinct space ⋮ Document retrieval with one wildcard ⋮ Optimal Encodings for Range Top-$$k$$, Selection, and Min-Max ⋮ Space-efficient indexes for forbidden extension queries ⋮ Access, Rank, and Select in Grammar-compressed Strings ⋮ Document listing on repetitive collections with guaranteed performance ⋮ In-place initializable arrays ⋮ Space-Efficient Frameworks for Top- k String Retrieval ⋮ String indexing for top-\(k\) close consecutive occurrences ⋮ Grammar compressed sequences with rank/select support ⋮ Ranked Document Retrieval with Forbidden Pattern ⋮ Encodings of Range Maximum-Sum Segment Queries and Applications ⋮ Compact Indexes for Flexible Top-$$k$$ Retrieval ⋮ Ranked Document Retrieval in External Memory ⋮ Time-Optimal Top-$k$ Document Retrieval ⋮ Gapped indexing for consecutive occurrences ⋮ The longest common substring problem ⋮ Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays. ⋮ Efficient computation of spatial queries over points stored in \(k^2\)-tree compact data structures ⋮ \(xkcd\)-repeats: a new taxonomy of repeats defined by their context diversity ⋮ Inducing enhanced suffix arrays for string collections ⋮ New space/time tradeoffs for top-\(k\) document retrieval on sequences ⋮ Lempel-Ziv compressed structures for document retrieval ⋮ Ranked document retrieval for multiple patterns ⋮ Ranked document selection ⋮ On hardness of several string indexing problems ⋮ Bottom-\(k\) document retrieval ⋮ Structural Pattern Matching - Succinctly. ⋮ On-the-Fly Array Initialization in Less Space ⋮ Practical Compact Indexes for Top-kDocument Retrieval
Uses Software
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 fully-compressed sequence representations
- Towards optimal range medians
- Efficient index for retrieving top-\(k\) most frequent documents
- Fast set intersection and two-patterns matching
- Succinct data structures for flexible text retrieval systems
- Two-dimensional substring indexing.
- On-line construction of suffix trees
- Improved compressed indexes for full-text document retrieval
- Constructing suffix arrays in linear time
- Space efficient linear time construction of suffix arrays
- Orthogonal Range Searching for Text Indexing
- Top-k Document Retrieval in External Memory
- Top-k Document Retrieval in Compact Space and Near-Optimal Time
- Wavelet Trees for All
- Towards an Optimal Space-and-Query-Time Index for Top-k Document Retrieval
- Document Listing for Queries with Excluded Pattern
- New Lower and Upper Bounds for Representing Sequences
- Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
- Alphabet-Independent Compressed Text Indexing
- Suffix Arrays: A New Method for On-Line String Searches
- Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
- An analysis of the Burrows—Wheeler transform
- Fast Algorithms for Finding Nearest Common Ancestors
- Mining Query Logs: Turning Search Usage Data into Knowledge
- Linear work suffix array construction
- Compressed Text Indexes with Fast Locate
- Compression, Indexing, and Retrieval for Massive String Data
- Rank/select operations on large alphabets
- Top-k Ranked Document Search in General Text Databases
- Cell Probe Lower Bounds and Approximations for Range Mode
- Optimal Trade-Offs for Succinct String Indexes
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- A unifying look at data structures
- Recursive Star-Tree Parallel Data Structure
- A Space-Economical Suffix Tree Construction Algorithm
- Design and implementation of an efficient priority queue
- Algorithms on Strings, Trees and Sequences
- A Generalized Suffix Tree and Its (Un)Expected Asymptotic Behaviors
- Jewels of Stringology
- Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
- Further Results on Generalized Intersection Searching Problems: Counting, Reporting, and Dynamization
- Space-Efficient Framework for Top-k String Retrieval Problems
- GENERALIZED INTERSECTION SEARCHING PROBLEMS
- Compressed text indexes
- An experimental investigation of set intersection algorithms for text searching
- Web data mining. Exploring hyperlinks, contents, and usage data.
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
