A graph-based multilevel partitioning scheme for reducing disk access cost of 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 - 4th International Conference/Exhibition on High Performance Computing in the Asia-Pacific Region, HPC-Asia 2000
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages812-817
Volume2
ISBN (Print)0769505902, 9780769505909
Publication statusPublished - 2000

Publication series

Name
Volume2

Conference

Title4th International Conference/Exhibition on High Performance Computing in the Asia-Pacific Region, HPC-Asia 2000
PlaceChina
CityBeijing
Period14 - 17 May 2000

Abstract

Spatial join queries usually access a large number of spatial data. The disk access cost of spatial join processing could be very high due to the large sizes of spatial data and the large number of spatial objects involved. A graph based multilevel data partitioning approach is proposed to partition objects into clusters for spatial join processing. Whenever the number of objects involved in a spatial join operation is greater than a threshold, say a hundred, the objects will be partitioned 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. The objects in a cluster are fetched together into memory and processed in a batch. Experiments have been conducted and the results have shown that our method can save 20-35% of disk access cost compared with the cases where no clustering or a little clustering is done.

Citation Format(s)

A graph-based multilevel partitioning scheme for reducing disk access cost of spatial join processing. / Xiao, Jitian; Zhang, Yanchun; Jia, Xiaohua.

Proceedings - 4th International Conference/Exhibition on High Performance Computing in the Asia-Pacific Region, HPC-Asia 2000. Vol. 2 Institute of Electrical and Electronics Engineers Inc., 2000. p. 812-817 843552.

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