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

Citation
Jt. Xiao et al., Clustering non-uniform-sized spatial objects to reduce I/O cost for spatial-join processing, COMPUTER J, 44(5), 2001, pp. 384-397
Citations number
33
Categorie Soggetti
Computer Science & Engineering
Journal title
COMPUTER JOURNAL
ISSN journal
00104620 → ACNP
Volume
44
Issue
5
Year of publication
2001
Pages
384 - 397
Database
ISI
SICI code
0010-4620(2001)44:5<384:CNSOTR>2.0.ZU;2-P
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 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.