Schedule of join operations to reduce I/O cost in spatial database systems

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

8 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)299-317
Journal / PublicationData and Knowledge Engineering
Volume35
Issue number3
Publication statusPublished - Dec 2000

Abstract

In this paper, we propose a graph-based cluster-sequencing method to minimize the I/O cost in spatial join processing. We first define the maximum overlapping (MO) order in a graph, proving that the problem of finding an MO order in a graph is NP-complete. Then, we propose an algorithm to find an approximation to MO order in a graph. We also prove that the approximation to MO order obtained from our method is close to the optimal result. Simulations have been conducted to demonstrate the saving of I/O cost in special join by using our method.

Citation Format(s)

Schedule of join operations to reduce I/O cost in spatial database systems. / Xiao, Jitian; Zhang, Yanchun; Jia, Xiaohua; Zhou, Xiaofang.

In: Data and Knowledge Engineering, Vol. 35, No. 3, 12.2000, p. 299-317.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review