Synonyms
Hierarchical regular-decomposition structures; Hierarchical spatial indexes; Quadtree variations
Definition
In general, the term quadtree refers to a class of representations of geometric entities (such as points, line segments, polygons, regions) in a space of two (or more) dimensions that recursively decompose the space containing these entities into blocks until the data in each block satisfy some condition (with respect, for example, to the block size, the number of block entities, the characteristics of the block entities, etc.).
In a more restricted sense, the term quadtree (octree) refers to a tree data structure in which each internal node has four (eight) children and is used for the representation of geometric entities in a two (three) dimensional space. The root of the tree represents the whole space/region. Each child of a node represents a subregion of the subregion of its parent. The subregions of the siblings constitute a partition of the parent’s regions.
Severa...
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Recommended Reading
Finkel R, Bentley JL. Quad trees: a data structure for retrieval on composite keys. Acta Informatica. 1974;4(1):1–9.
Samet H. The design and analysis of spatial data structures. Reading: Addison Wesley; 1990.
Klinger A, Dyer C. Experiments on picture representation using regular decomposition. Comput Graphics Image Process. 1976;5(1):68–105.
Gargantini I. An effective way to represent quadtrees. Commun ACM. 1982;25(12):905–10.
Samet H. Foundations of multidimensional and metric data structures. Amsterdam: Morgan Kaufmann; 2006.
Manouvrier M, Rukoz M, Jomier G. Quadtree-based image representation and retrieval. In: Spatial databases: technologies, techniques and trends. Hershey: Idea Group Publishing; 2005. p. 81–106.
Vassilakopoulos M, Manolopoulos Y, Economou K. Overlapping quadtrees for the representation of similar images. Image Vis Comput. 1993;11(5): 257–62.
Tzouramanis T, Vassilakopoulos M, Manolopoulos Y. Benchmarking access methods for time-evolving regional data. Data Knowl Eng. 2004;49(3): 243–86.
Eppstein D, Goodrich MT, Sun JZ. The skip quadtree: a simple dynamic data structure for multidimensional data. In: Proceedings of the 21st Annual Symposium on Computational Geometry; 2005. p. 296–305.
Kothuri R, Ravada S, Abugov D. Quadtree and r-tree. indexes in oracle spatial: a comparison using gis data. In: Proceedings of the ACM SIGMOD Inter-national Conference on Management of Data; 2002. p. 546–57.
Brabec F, Samet H. Spatial index demos. http://donar.umiacs.umd.edu/quadtree/index.html. Last accessed in Dec 2016.
Samet H. Applications of spatial data structures. Reading: Addison Wesley; 1990.
Shaffer CA, Brown PR. A paging scheme for pointer-based quadtrees. In: Abel D, Chin Ooi B, editors. Advances in Spatial Databases, Proceedings of the 3rd International Symposium on Large Spatial Databases; 1993. p. 89–104.
Kim YJ, Patel JM. Rethinking choices for multi-dimensional point indexing: making the case for the often ignored quadtree. In: Proceedings of the 3rd Biennial Conference on Innovative Data Systems Research; 2007. p. 281–91. http://cidrdb.org/2007Proceedings.zip
Vassilakopoulos M, Manolopoulos Y. External balanced regular (x-BR) trees: new structures for very large spatial databases. In: Fotiadis DI, Nikolopoulos SD, editors. Advances in informatics. Singapore: World Scientific; 2000. p. 324–33.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Section Editor information
Rights and permissions
Copyright information
© 2018 Springer Science+Business Media, LLC, part of Springer Nature
About this entry
Cite this entry
Vassilakopoulos, M., Tzouramanis, T. (2018). Quadtrees (and Family). In: Liu, L., Özsu, M.T. (eds) Encyclopedia of Database Systems. Springer, New York, NY. https://doi.org/10.1007/978-1-4614-8265-9_286
Download citation
DOI: https://doi.org/10.1007/978-1-4614-8265-9_286
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4614-8266-6
Online ISBN: 978-1-4614-8265-9
eBook Packages: Computer ScienceReference Module Computer Science and Engineering