Window Query Processing in Linear Quadtrees |
| |
Authors: | Ashraf Aboulnaga Walid G. Aref |
| |
Affiliation: | (1) Computer Sciences Department, University of Wisconsin - Madison, 1210 West Dayton Street, Madison, WI 53706, USA;(2) Department of Computer Sciences, Purdue University, 1398 Computer Science Building, West Lafayette, IN 47907, USA |
| |
Abstract: | The linear quadtree is a spatial access method that is built by decomposing the spatial objects in a database into quadtree blocks and storing these quadtree blocks in a B-tree. The linear quadtree is very useful for geographic information systems because it provides good query performance while using existing B-tree implementations. An algorithm and a cost model are presented for processing window queries in linear quadtrees. The algorithm can handle query windows of any shape in the general case of spatial databases with overlapping objects. The algorithm recursively decomposes the space into quadtree blocks, and uses the quadtree blocks overlapping the query window to search the B-tree. The cost model estimates the I/O cost of processing window queries using the algorithm. The cost model is also based on a recursive decomposition of the space, and it uses very simple parameters that can easily be maintained in the database catalog. Experiments with real and synthetic data sets verify the accuracy of the cost model. |
| |
Keywords: | spatial databases spatial access methods quadtrees window queries GIS |
本文献已被 SpringerLink 等数据库收录! |
|