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.