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
Pages (from-to)1400-1421
Number of pages22
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number6
StatePublished - Nov 2002
Externally publishedYes


  • 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