Title

Clustering non-uniform-sized spatial objects to reduce i/o cost for spatial-join processing

Document Type

Journal Article

Publisher

Algorithms, Computational complexity, Computer simulation, Graph theory, Matrix algebra, Query languages

Faculty

Computing, Health and Science

School

Computer and Information Science

RAS ID

799

Comments

Originally published as: Xiao, J., Zhang, Y., & Jia, X. (2001). Clustering non-uniform-sized spatial objects to reduce I/O cost for spatial-join processing. The Computer Journal, 44(5), 384-397. Original article available here

Abstract

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 filter-and-refine strategy is usually used to reduce the computing cost of spatial join when the number of spatial objects is large. In this paper we propose 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 algorithm 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 brought together into the main memory for the refinement process, and the I/O cost of fetching objects into memory can, be reduced. Experiments have been conducted and the results have shown that our method can save 20-35% of I/O cost compared to the cases where no clustering or a little clustering is done.

DOI

10.1093/comjnl/44.5.384

 
COinS
 

Link to publisher version (DOI)

10.1093/comjnl/44.5.384