Space efficient hierarchical structures: relatively addressed compact quadtrees for GISs

摘要

Traditional pointer-based quadtree data structures are generally viewed as inferior to linear quadtree data structures when used in geographical information systems (GISs). This is largely due to their space inefficiency and to the fact that they are difficult to manage on secondary storage. In this paper, an improved, pointerbased quadtree called the relatively addressed compact quadtree (RACQ) is presented which possesses a pointer system and hierarchical structure. The RACQ solves the two problems associated with traditional pointer-based quadtrees.