Efficient Join-Index-Based Spatial-Join Processing: A Clustering Approach

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

Abstract

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.
BibTeX
@article{shekhar2002efficient,
  author = {Shashi Shekhar and Chang-Tien Lu and Sanjay Chawla and Sivakumar Ravada},
  title = {{Efficient Join-Index-Based Spatial-Join Processing: A Clustering Approach}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2002},
  url = {https://openreview.net/forum?id=gahXsZ9JnS},
}

Loading related content...

Figure