Succinct color searching in one dimension

DOI10.4230/LIPICS.ISAAC.2017.30MaRDI QIDQ5136249zbMATH OpenOpenAlexFDO

Authors Hicham El-Zein, J. Ian Munro, Yakov Nekrich

Publication date 25 November 2020

Full work available at URL https://dblp.uni-trier.de/db/conf/isaac/isaac2017.html#El-ZeinMN17

zbMATH Keywords

computational geometryrange searchingsuccinct data structures

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Succinct dynamic one-dimensional point reporting
• Optimal color range reporting in one dimension
• Colored Range Searching in Linear Space
• Colored range queries and document retrieval
• scientific article; zbMATH DE number 1830754

Cites work

• A lower bound for finding predecessors in Yao's cell probe model
• Adaptive and approximate orthogonal range counting
• Approximate range emptiness in constant time and optimal space
• Colored range queries and document retrieval
• Counting Colours in Compressed Strings
• Dynamic Compressed Strings with Random Access
• Efficient range searching for categorical and plain data
• Further Results on Generalized Intersection Searching Problems: Counting, Reporting, and Dynamization
• GENERALIZED INTERSECTION SEARCHING PROBLEMS
• scientific article; zbMATH DE number 2119724 (Why is no real title available?)
• New upper bounds for generalized intersection searching problems
• Optimal bounds for the predecessor problem
• Optimal color range reporting in one dimension
• Optimal succinctness for range minimum queries
• Random access to grammar-compressed strings
• Succinct and Implicit Data Structures for Computational Geometry
• Succinct geometric indexes supporting point location queries
• Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets
• Succinct indices for range queries with applications to orthogonal range maxima
• Surpassing the information theoretic bound with fusion trees
• Time-space trade-offs for predecessor search

Cited in

(10)

• Succinct data structures for nearest colored node in a tree
• Approximate query processing over static sets and sliding windows
• Data structures for categorical path counting queries
• Optimal color range reporting in one dimension
• Approximate query processing over static sets and sliding windows
• A constant-time colored choice dictionary with almost robust iteration
• Succinct dynamic one-dimensional point reporting
• Color-distance oracles and snippets
• Adaptive data structures for 2D dominance colored range counting
• On approximate colored path counting

This page was built for publication: Succinct color searching in one dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136249)