Faster compressed quadtrees

G. de Bernardo, T. Gagie, S. Ladra, G. Navarro, and D. Seco, "Faster compressed quadtrees", Journal of Computer and System Sciences, Vol. 131, pp. 86 - 104, Feb. 2023, doi: 10.1016/j.jcss.2022.09.001

Abstract

[Abstract]: Real-world point sets tend to be clustered, so using a machine word for each point is wasteful. In this paper we first show how a compact representation of quadtrees using O(1) bits per node can break this bound on clustered point sets, while offering efficient range searches. We then describe a new compact quadtree representation based on heavy-path decompositions, which supports queries faster than previous compact structures. We present experimental evidence showing that our structure is competitive in practice.

Keywords

Clustered points
Compact data structures
Heavy-path decomposition
Quadtrees
Range queries

Description

©2023 Elsevier B.V. All rights reserved. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/byncnd/ 4.0/. This version of the article has been accepted for publication in Future Generation Computer Systems. The Version of Record is available online at https:// doi.org/10.1016/j.jcss.2022.09.001

Versión aceptada

An early partial version of this paper appeared in Proc. of the Data Compression Conference 2015.