ANALYTICAL COMPARISON OF 2 SPATIAL DATA-STRUCTURES

Region Quadtrees and Bintrees are two structures used in GIS and spati al databases. The expected space performances of these two trees are p resented and compared. Analysis is based on the general assumption tha t the storage requirements of internal and external nodes differ, as w ell as on a parametric model of binary random images. Initially, formu lae that express the average total storage performance of the two tree s are given. For each level of the Quadtree, formulae for the average numbers of internal, external white and external black nodes follow. N ext, for each level of the Quadtree, the relationship between each nod e category of the two trees is presented. Based on the formulae develo ped, we study how the storage requirements of the two trees differ for each Quadtree level. Finally, using the above results, we reach concl usions about the storage efficiency of the most popular implementation s and the inverted variations of these two (structures that index pict orial databases).