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

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

doi:10.1109/TKDE.2002.1047776

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

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

Research output: Contribution to journal › Article › peer-review

13 Scopus citations

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.

Original language	English (US)
Pages (from-to)	1400-1421
Number of pages	22
Journal	IEEE Transactions on Knowledge and Data Engineering
Volume	14
Issue number	6
DOIs	https://doi.org/10.1109/TKDE.2002.1047776
State	Published - 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.

Keywords

Join index
Join processing
Optimal page access sequence
Spatial join

Publisher link

10.1109/TKDE.2002.1047776

Find It

Find It at U of M Libraries

Cite this

@article{fad979456594445181fcf30366b1d1a2,

title = "Efficient join-index-based spatial-join processing: A clustering approach",

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.",

keywords = "Join index, Join processing, Optimal page access sequence, Spatial join",

author = "Shashi Shekhar and Lu, \{Chang Tien\} and Sanjay Chawla and Sivakumar Ravada",

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.",

year = "2002",

month = nov,

doi = "10.1109/TKDE.2002.1047776",

language = "English (US)",

volume = "14",

pages = "1400--1421",

journal = "IEEE Transactions on Knowledge and Data Engineering",

issn = "1041-4347",

publisher = "IEEE Computer Society",

number = "6",

}

TY - JOUR

T1 - Efficient join-index-based spatial-join processing

T2 - A clustering approach

AU - Shekhar, Shashi

AU - Lu, Chang Tien

AU - Chawla, Sanjay

AU - Ravada, Sivakumar

N1 - 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.

PY - 2002/11

Y1 - 2002/11

N2 - 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.

AB - 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.

KW - Join index

KW - Join processing

KW - Optimal page access sequence

KW - Spatial join

UR - https://www.scopus.com/pages/publications/0036857123

UR - https://www.scopus.com/pages/publications/0036857123#tab=citedBy

U2 - 10.1109/TKDE.2002.1047776

DO - 10.1109/TKDE.2002.1047776

M3 - Article

AN - SCOPUS:0036857123

SN - 1041-4347

VL - 14

SP - 1400

EP - 1421

JO - IEEE Transactions on Knowledge and Data Engineering

JF - IEEE Transactions on Knowledge and Data Engineering

IS - 6

ER -

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

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this