Efficient join-index-based spatial-join processing: A clustering approach

Shashi Shekhar, Chang Tien Lu, Sanjay Chawla, Sivakumar Ravada

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


A join-index is a data structure used for processing join queries in databases. Join-indices use precomputation techniques to speed up online query processing and are useful for data sets which are updated infrequently. The I/O cost of join computation using a join-index with limited buffer space depends primarily on the page-access sequence used to fetch the pages of the base relations. Given a join-index, we introduce a suite of methods based on clustering to compute the joins. We derive upper bounds on the length of the page-access sequences. Experimental results with Sequoia 2000 data sets show that the clustering method outperforms existing methods based on sorting and online-clustering heuristics.

Original languageEnglish (US)
Pages (from-to)1400-1421
Number of pages22
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number6
StatePublished - Nov 2002

Bibliographical note

Funding Information:
This work is sponsored in part by the US Army High Performance Computing Research Center under the auspices of the Department of the Army, Army Research Laboratory cooperative agreement number DAAH04-95-2-0003/contract number DAAH04-95-C-0008, the content of which does not necessarily reflect the position or the policy of the government and no official endorsement should be inferred. This work was also supported in part by US National Science Foundation grant #9631539. The authors would like to thank Kim Koffolt for improving the readability of this paper. We also would like to thank Xuan Liu, Xinhong Tan, and Weili Wu for their technical comments.


  • Join index
  • Join processing
  • Optimal page access sequence
  • Spatial join


Dive into the research topics of 'Efficient join-index-based spatial-join processing: A clustering approach'. Together they form a unique fingerprint.

Cite this