I/O-efficient data structures for colored range and prefix reporting

MaRDI QIDQ5743422zbMATH OpenFDO

Authors Kasper Green Larsen, Rasmus Pagh

Publication date 10 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=2095165

Mathematics Subject Classification ID

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

Recommendations

• Near-optimal range reporting structures for categorical data
• Optimal color range reporting in one dimension
• Colored range queries and document retrieval
• Colored Range Searching in Linear Space
• Dynamic range reporting in external memory

Cites work

• scientific article; zbMATH DE number 5506205 (Why is no real title available?)
• scientific article; zbMATH DE number 1256735 (Why is no real title available?)
• scientific article; zbMATH DE number 1947435 (Why is no real title available?)
• A log log n data structure for three-sided range queries
• Algorithms for parallel memory, I: Two-level memories
• Cache-oblivious algorithms
• Cache-oblivious data structures for orthogonal range searching
• Cache-oblivious planar orthogonal range searching and counting
• Cache-oblivious range reporting with optimal queries requires superlinear space
• Dynamic 3-sided planar range queries with expected doubly logarithmic time
• Dynamic 3-sided planar range queries with expected doubly-logarithmic time
• External Memory Range Reporting on a Grid
• Fast prefix search in little space, with applications
• I/O-Efficient Point Location in a Set of Rectangles
• Improved space bounds for cache-oblivious range reporting
• On Dominance Reporting in 3D
• Optimal static range reporting in one dimension
• Orthogonal Range Reporting in Three and Higher Dimensions
• Priority Search Trees
• Supporting random access in files of variable length records
• Surpassing the information theoretic bound with fusion trees
• Using hashing to solve the dictionary problem

Cited in

(8)

• Dynamic 3-sided planar range queries with expected doubly-logarithmic time
• I/O-efficient 2-d orthogonal range skyline and attrition priority queues
• Colored range queries and document retrieval
• scientific article; zbMATH DE number 7561469 (Why is no real title available?)
• I/O-optimal categorical 3-sided skyline queries
• Partial sums on the ultra-wide word RAM
• Predecessor on the Ultra-Wide Word RAM
• Near-optimal range reporting structures for categorical data

This page was built for publication: I/O-efficient data structures for colored range and prefix reporting

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