Space efficient data structures for dynamic orthogonal range counting

DOI10.1016/J.COMGEO.2013.08.007MaRDI QIDQ390134zbMATH OpenOpenAlexFDO

Authors Meng He, J. Ian Munro

Publication date 22 January 2014

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2013.08.007

zbMATH Keywords

dynamic data structuregeometric data structureorthogonal range countingsuccinct data structure

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Review text

\textit{Y. Nekrich} [Comput. Geom. 42, No. 4, 342--351 (2009; Zbl 1170.68012)] designed a data structure of a linear space with improved query time (cf. [\textit{B. Chazelle}, SIAM J. Comput. 17, No. 3, 427--462 (1988; Zbl 0679.68074)]). The authors study the problem of designing a linear space data structure that matches Nekrich's query time [loc. cit.] while providing a faster support for updates. The authors also obtain new results for the case in which the points are on a grid, and for supporting range counting on an integer sequence a succinct data structure also obtained.

Recommendations

• Space Efficient Data Structures for Dynamic Orthogonal Range Counting
• Orthogonal range searching in linear and almost-linear space
• Orthogonal Range Searching in Linear and Almost-Linear Space
• Space efficient dynamic orthogonal range reporting
• Space efficient dynamic orthogonal range reporting

Cites work

• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• Adaptive searching in succinctly encoded binary relations and tree-structured documents
• Adding range restriction capability to dynamic data structures
• Compressed representations of sequences and full-text indexes
• Compressing and indexing labeled trees, with applications
• Decomposable searching problems
• Dynamic entropy-compressed sequences and full-text indexes
• Dynamic range selection in linear space
• scientific article; zbMATH DE number 5485435 (Why is no real title available?)
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 1830754 (Why is no real title available?)
• Improved data structures for the orthogonal range successor problem
• New Data Structures for Orthogonal Range Queries
• Optimal External Memory Interval Management
• Orthogonal range searching in linear and almost-linear space
• Rank and select revisited and extended
• Rank/select on dynamic compressed sequences and applications
• Space Efficient Data Structures for Dynamic Orthogonal Range Counting
• Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
• Succinct indexes for strings, binary relations and multilabeled trees
• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• Succinct representation of labeled graphs
• The cell probe complexity of dynamic range counting

Cited in

(8)

• Dynamic path queries in linear space
• Internal dictionary matching
• Resolving SINR Queries in a Dynamic Setting
• Resolving SINR queries in a dynamic setting
• Space Efficient Data Structures for Dynamic Orthogonal Range Counting
• Cache-oblivious data structures for orthogonal range searching
• scientific article; zbMATH DE number 7740901 (Why is no real title available?)
• Dynamic layers of maxima with applications to dominating queries

This page was built for publication: Space efficient data structures for dynamic orthogonal range counting

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