Match Based SJP Cluster sequencing and scheduling in spatial databases

Document Type

Conference Proceeding


Faculty of Computing, Health and Science


School of Computer and Security Science




Xiao, J. (2003). Match Based SJP Cluster sequencing and scheduling in spatial databases. The 2nd International Conference on Computational Intelligence, Robotics and Autonomous Systems.


The spatial join is an operation that combines two sets of spatial data by their spatial relationships. It is one of the most important operations in spatial databases. The cost of spatial join could be very high due to the large sizes of spatial objects and the computation-intensive spatial operations. In spatial join processing (SJP), a common method to minimize the I/O cost is to partition the spatial objects into clusters and then schedule the processing of the clusters such that the number of times the same objects to be fetched into memory can be minimized. [1] proposed a cluster-sequencing method to minimize the I/O cost in spatial join processing. The key issue behind that method is how to produce a better sequence of clusters to guide the scheduling. This paper proposes a new efficient algorithm that gives us a better sequence than the original algorithm does in the sense that over 16% of the fetching time used for fetching those overlapping objects of clusters can be saved. Simulations have been conducted to demonstrate the saving of 1/0 cost in spatial join by using the new sequencing method.

This document is currently not available here.