|
|||||
|
|
A schedule of join operations to reduce I/O cost in spatial database systems |
|
| Authors: | Jitian Yanchun Xiaohua Xiaofang |
| Affiliation: | a Department of Mathematics and Computing, University of Southern Queensland, Toowoomba, Qld 4350, Australia b Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong c Department of Computer Science and Electrical Engineering, University of Queensland, Brisbane, Qld 4072, Australia |
| 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 spatial join by using our method. |
| Keywords: | Spatial databases Spatial joins Data partitioning Scheduling |
| 本文献已被 ScienceDirect 等数据库收录！ | |