Efficient Region Query Processing by Optimal Page Ordering

摘要

A number of algorithms of clustering spatial data for reducing the number of disk seeks required to process spatial queries have been developed. One of the algorithms is the scheme of page ordering, which is concerned with the order of pages in one-dimensional storage for storing two-dimensional spatial data. The space filling curves, especially the Hilbert curves, have been so far used to impose an order on all of pages. Page ordering based on the space filling curves, however, does not take into account the uneven distribution of spatial objects and the types of spatial queries. We will develop a cost model to define the page ordering problem based on performance measurement and then find out the method of page ordering for efficiently processing region queries in static databases. The experimental results will show that the newly proposed ordering method achieves better clustering than older methods.