Multilevel data clustering for spatial join processing

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationProceedings - 1999 International Symposium on Database Applications in Non-Traditional Environments (DANTE '99)
EditorsYahiko Kambayasbi , Hiroki Takakura
PublisherIEEE
Pages218-225
Number of pages8
ISBN (Print)0-7695-0496-5
Publication statusPublished - Nov 1999

Publication series

NameProceedings - 1999 International Symposium on Database Applications in Non-Traditional Environments, DANTE 1999

Conference

Title1999 International Symposium on Database Applications in Non-Traditional Environments, DANTE 1999
PlaceJapan
CityKyoto
Period28 - 30 November 1999

Abstract

The I/O cost of spatial join processing could be very high due to the large sizes of spatial objects and the large number of spatial objects involved. Spatial joins are usually performed by the filter-and-refinement approach. Although there exists a variety of algorithms for realizing the filter step of the join processing for large spatial data sets, not much research has been done to improve the performance of the refinement step. By clustering the output of the filter step, we are able to reduce the total number of times that spatial objects are repeatedly loaded during the refinement step, thus to reduce the I/O cost of the refinement step. In this paper, a multilevel data partitioning approach is proposed to partition objects into clusters for spatial join processing. Whenever the number of objects is greater than a threshold, say a hundred, the objects will be clustered through a multilevel scheme, i.e., first coarsening, then partitioning, and finally uncoarsening back to the original object sets, which can be further partitioned using the known partitioning methods. Experiments have been conducted and the results have shown that our method can save 20-35% of I/O cost compared with the cases where no clustering or a little clustering is done.

Citation Format(s)

Multilevel data clustering for spatial join processing. / Xiao, Jitian; Zhang, Yanchun; Jia, Xiaohua.

Proceedings - 1999 International Symposium on Database Applications in Non-Traditional Environments (DANTE '99). ed. / Yahiko Kambayasbi ; Hiroki Takakura . IEEE, 1999. p. 218-225 (Proceedings - 1999 International Symposium on Database Applications in Non-Traditional Environments, DANTE 1999).

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review