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

zbMATH Open1422.68049MaRDI QIDQ5743422FDOQ5743422

Authors: Kasper Green Larsen, Rasmus Pagh 

Publication date: 10 May 2019

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

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

Mathematics Subject Classification ID

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

Cites Work

• Cache-oblivious algorithms
• Fast prefix search in little space, with applications
• Priority Search Trees
• Optimal static range reporting in one dimension
• Surpassing the information theoretic bound with fusion trees
• Supporting random access in files of variable length records
• Cache-oblivious data structures for orthogonal range searching
• On Dominance Reporting in 3D
• Title not available (Why is that?)
• Title not available (Why is that?)
• Cache-oblivious planar orthogonal range searching and counting
• Algorithms for parallel memory, I: Two-level memories
• Title not available (Why is that?)
• Improved space bounds for cache-oblivious range reporting
• Cache-oblivious range reporting with optimal queries requires superlinear space
• A log log n data structure for three-sided range queries
• Orthogonal Range Reporting in Three and Higher Dimensions
• Dynamic 3-sided planar range queries with expected doubly-logarithmic time
• External Memory Range Reporting on a Grid
• Dynamic 3-sided planar range queries with expected doubly logarithmic time
• I/O-Efficient Point Location in a Set of Rectangles
• 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
• Title not available (Why is that?)
• 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)