Faster compressed quadtrees

DOI10.1016/J.JCSS.2022.09.001MaRDI QIDQ2084740OpenAlexFDO

Authors Guillermo de Bernardo, Travis Gagie, Susana Ladra, Gonzalo Navarro, Diego Seco

Publication date 13 October 2022

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.2785

zbMATH Keywords

heavy-path decompositionrange queriescompact data structuresquadtreesclustered points

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• Dynamic smooth compressed quadtrees
• Efficient Coding of Quadtree Nodes
• Quadtree representation and compression of spatial data
• The space efficiency of quadtrees

Cites work

• scientific article; zbMATH DE number 3415422 (Why is no real title available?)
• 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
• 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: Generating all combinations and partitions. Fasc. 4: Generating all trees. History of combinatorial generation.
• Time-space trade-offs for predecessor search
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths

Cited in

(18)

• Quadtree representation and compression of spatial data
• Efficient computation of spatial queries over points stored in \(k^2\)-tree compact data structures
• Dynamic smooth compressed quadtrees
• Simple and Efficient Traversal Methods for Quadtrees and Octrees
• SP-quadtree: an approach of data structuring for parallelization of spatial data
• GraCT: a grammar-based compressed index for trajectory data
• Evaluating regular path queries on compressed adjacency matrices
• Fringed-quadtrees: a new kind of data structure
• scientific article; zbMATH DE number 3907790 (Why is no real title available?)
• A generalized comparison of linear representations of thematic layers
• How to efficiently generate PNR representation of a qualitative geofield
• \(L\) curve for spherical triangle region quadtrees
• Entropy-bounded representation of point grids
• Efficient Coding of Quadtree Nodes
• Compressed data structures for range searching
• Entropy-bounded representation of point grids
• Kinetic compressed quadtrees in the black-box model with applications to collision detection for low-density scenes
• Analysis of the worst case space complexity of a PR quadtree

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)