Skip Navigation

The Computer Journal 2001 44(5):384-397; doi:10.1093/comjnl/44.5.384
© 2001 by British Computer Society
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (1)
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Xiao, J.
Right arrow Articles by Jia, X.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Clustering Non-uniform-sized Spatial Objects to Reduce I/O Cost for Spatial-join Processing

Jitian Xiao1, Yanchun Zhang2 and Xiaohua Jia3

1 School of Computer and Information Science, Edith Cowan University, Mount Lawley, Perth, WA 6050, Australia Email: j.xiao@ecu.edu.au 2 Department of Mathematics and Computing, University of Southern Queensland, Toowoomba Qld 4350, Australia 3 Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong

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, thus, 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.

Received 26 October, 2000. Revised 6 May, 2001.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.