Speeding up bulk-loading of quadtrees
Gı́sli R. Hjaltason, Hanan Samet, Yoram J. Sussmann · 1997
Spatial indexes, such as the PMR quadtree, are important in spatial databases for efficient execution of queries involving spatial constraints, especially when the queries involve spatial joins. We investigate the issue of speeding up building PMR quadtrees for a set of objects and develop two approaches to achieve this goal. In an empirical study, we find that the better method of the two offers significant improvements in execution time, and present evidence of the usefulness of spatial indexing for executing spatial join queries. 1 Introduction Traditional database systemsemploy indexes on alphanumeric data, usually based on the B-tree, to facilitate efficient query handling. Typically, the database system allows the users to designate which attributes (data fields) need to be indexed. However, advanced query optimizers also have the ability to create indexes on unindexed data or temporary results (i.e., results from a part of the query) as needed. In order for this to be worthwhil...