Analytical comparison of two spatial data structures

摘要

Region Quadtrees and Bintrees are two structures used in GIS and spatial databases. The expected space performances of these two trees are presented and compared. Analysis is based on the general assumption that the storage requirements of internal and external nodes differ, as well as on a parametric model of binary random images. Initially, formulae that express the average total storage performance of the two trees are given. For each level of the Quadtree, formulae for the average numbers of internal, external white and external black nodes follow. Next, for each level of the Quadtree, the relationship between each node category of the two trees is presented. Based on the formulae developed, we study how the storage requirements of the two trees differ for each Quadtree level. Finally, using the above results, we reach conclusions about the storage efficiency of the most popular implementations and the inverted variations of these two trees (structures that index pictorial databases).