Faster compressed quadtrees
In geographic information systems (GIS), graphics, and computational geometry querying, storing and processing of two-dimensional points sets is of fundamental importance. In such cases the size of used data structures, measured in machine words, is linear in the number of points. If the points are distributed randomly and uniform over the grid we can use \(O(n \log u)\) bits but there is a possibility to use quadtrees to perform better. Quadtrees are considered as queries of points' coordinates along a root-to-leaf path per point. When the clusters of points are represented, some close points in a cluster share long parts of their common path. When quadtrees are repesented by pointers they overall require \(\Omega(n \log u)\) bits but if it is based on succinct trees paths they use \(O (1)\) bits per quadtree node. In the paper the authors introduce a new space-efficient representation of quadtrees with heavy-path decompositions. Such structures are able to represent a quadtree on \(n\) points using an \(u \times u\) grid with \(O (1)\) bits per quadtree node. It also locates query performance in \(O (\log n)\) time complexity. The paper shows a space analysis of quadtree data structures showing that compressed quadtrees can use \(o(n \log u)\) bits of space on clustered points. The compressed data quadtree structure with heavy-path decomposition with one-step navigation over multiple edges can speed up the query processing. The whole paper is divided into 8 sections. Section 2 explains the theoretical details of compressed quadtree data structures, the next section develops a space analysis of quadtree data structures, whereas Sections 4 and 5 focus on a detailed description of such new structure and present new query algorithms. In Section 6 we have some practical improvements and Section 7 gives results of experiments. The paper is concluded with Section 8.
- A data structure for dynamic trees
- A practical succinct dynamic graph representation
- An effective way to represent quadtrees
- Fast compressed tries through path decompositions
- Foundations of multidimensional and metric data structures.
- Fully functional static and dynamic succinct trees
- scientific article; zbMATH DE number 3415422 (Why is no real title available?)
- Practical entropy-compressed rank/select dictionary
- Quad-K-d trees
- SKIP QUADTREES: DYNAMIC DATA STRUCTURES FOR MULTIDIMENSIONAL POINT SETS
- Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
- The art of computer programming. Vol. 4, Fasc. 0--4. Fasc. 0: Introduction to combinatorial algorithms and Boolean functions. Fasc. 1: Bitwise tricks \& techniques, binary decision diagrams. Fasc. 2: Generating all tuples and permutations. Fasc. 3: Genera
- Time-space trade-offs for predecessor search
- Trans-dichotomous algorithms for minimum spanning trees and shortest paths
- Analysis of the worst case space complexity of a PR quadtree
- GraCT: a grammar-based compressed index for trajectory data
- Efficient computation of spatial queries over points stored in \(k^2\)-tree compact data structures
- A generalized comparison of linear representations of thematic layers
- Compressed data structures for range searching
- Kinetic compressed quadtrees in the black-box model with applications to collision detection for low-density scenes
- SP-quadtree: an approach of data structuring for parallelization of spatial data
- Entropy-bounded representation of point grids
- Quadtree representation and compression of spatial data
- scientific article; zbMATH DE number 3907790 (Why is no real title available?)
- Entropy-bounded representation of point grids
- scientific article; zbMATH DE number 1156715 (Why is no real title available?)
- Simple and Efficient Traversal Methods for Quadtrees and Octrees
- Dynamic smooth compressed quadtrees
- How to efficiently generate PNR representation of a qualitative geofield
- Fringed-quadtrees: a new kind of data structure
- Efficient Coding of Quadtree Nodes
- Evaluating regular path queries on compressed adjacency matrices
- L curve for spherical triangle region quadtrees
This page was built for publication: Faster compressed quadtrees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2084740)
