Clustering Multidimensional Extended Objects to Speed Up Execution of Spatial Queries

http://www.springerlink.com/We present a cost-based adaptive clustering method to improve average performance of spatial queries (intersection, containment, enclosure queries) over large collections of multidimensional extended objects (hyper-intervals or hyper-rectangles). Our object clustering strategy is based on a cost model taking into account the spatial object distribution, the query distribution, and a set of database and system parameters affecting the query performance : object size, access time, transfer and verification costs. We also employ a new grouping criterion to group objects in clusters, more efficient than traditional approaches based on minimum bounding in all dimensions. Our cost model is flexible and can accommodate different storage scenarios : in-memory or disk-based. Experimental evaluations show that our approach is efficient in a number of situations involving large spatial databases with many dimensions