Back to Search
Start Over
Faster compressed quadtrees.
- Source :
-
Journal of Computer & System Sciences . Feb2023, Vol. 131, p86-104. 19p. - Publication Year :
- 2023
-
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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *QUADTREES
*POINT set theory
*MULTICASTING (Computer networks)
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 131
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 159601463
- Full Text :
- https://doi.org/10.1016/j.jcss.2022.09.001