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

In this paper, we propose a graph-based cluster-sequencing method to minimi ze the I/O cost in spatial join processing. We first define the maximum ove rlapping (MO) order in a graph, proving that the problem of finding an MO o rder in a graph is NP-complete. Then, we propose an algorithm to find an ap proximation 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. Simulati ons have been conducted to demonstrate the saving of I/O cost in spatial jo in by using our method. (C) 2000 Elsevier Science B.V. All rights reserved.