Clustering non-uniform-sized spatial objects to reduce I/O cost for spatial-join processing

The cost of spatial-join processing can be very high due to the large sizes of spatial objects and the computation-intensive spatial operations. A fil ter-and-refine strategy is usually used to reduce the computing cost of spa tial join when the number of spatial objects is large. In this paper we pro pose a method that aims to minimize the I/O cost at the refinement step. A graph model is introduced to formalize the I/O cost, and a matrix-based alg orithm is developed to cluster objects (data) such that the objects in the same cluster are closely related. The objects in the same cluster will be b rought together into the main memory for the refinement process, and the I/ O cost of fetching objects into memory can, thus, be reduced. Experiments h ave been conducted and the results have shown that our method can save 20-3 5% of I/O cost compared to the cases where no clustering or a little cluste ring is done.