Space Efficient Multi-dimensional Range Reporting

DOI10.1007/978-3-642-02882-3_22MaRDI QIDQ5323066zbMATH OpenOpenAlexFDO

Authors Yakov Nekrich, Marek Karpinski

Publication date 23 July 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02882-3_22

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• A data structure for multi-dimensional range reporting
• Orthogonal range reporting, query lower bounds, optimal structures in 3-d, and higher-dimensional improvements
• Dynamic range reporting in external memory
• Space efficient dynamic orthogonal range reporting
• Space efficient dynamic orthogonal range reporting

Cites work

• A data structure for multi-dimensional range reporting
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• Decomposable searching problems
• Fractional cascading. I: A data structuring technique
• scientific article; zbMATH DE number 1256735 (Why is no real title available?)
• scientific article; zbMATH DE number 910894 (Why is no real title available?)
• Linear space data structures for two types of range search
• Multidimensional divide-and-conquer
• On Dominance Reporting in 3D
• Preserving order in a forest in less than logarithmic time and linear space
• Space efficient dynamic orthogonal range reporting
• Space Efficient Multi-dimensional Range Reporting

Cited in

(12)

• Dictionary matching with a bounded gap in pattern or in text
• Dictionary matching with uneven gaps
• Dynamic range reporting in external memory
• A data structure for multi-dimensional range reporting
• Space Efficient Multi-dimensional Range Reporting
• Orthogonal range reporting, query lower bounds, optimal structures in 3-d, and higher-dimensional improvements
• Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
• scientific article; zbMATH DE number 7651193 (Why is no real title available?)
• Linear space adaptive data structures for planar range reporting
• Four-dimensional dominance range reporting in linear space
• Quantum data structure for range minimum query
• Internal pattern matching in small space and applications

This page was built for publication: Space Efficient Multi-dimensional Range Reporting

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