Efficient Join Processing Using Partial Precomputation

In this paper, we generalize conventional join indexes to a cluster-based join index, in which objects are grouped into clusters based on proximity. Each record of our join index represents a pair of clusters in which the join condition is satisfied by some members of the cluster. This strategy is e...

Full description

Saved in:
Bibliographic Details
Published in:Knowledge and information systems 1999-11, Vol.1 (4), p.481-514
Main Authors: Tan, Kian-Lee, Goh, Cheng Hian, Lee, Mong Li, Ooi, Beng Chin
Format: Article
Language:English
Subjects:
Clusters
Information systems
Intersections
Proximity
Query processing
Retrieval
Strategy
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we generalize conventional join indexes to a cluster-based join index, in which objects are grouped into clusters based on proximity. Each record of our join index represents a pair of clusters in which the join condition is satisfied by some members of the cluster. This strategy is especially useful for spatial and high-dimensional databases because of their typically large data volume and complex operations. Our approach leverages on the structure of R-trees by exploiting the internal nodes of an R-tree in effectively determining the precomputed clusters which can be used in our join index. By varying the size of the cluster, we are able to fine-tune the join index to achieve a balance between update cost and retrieval cost to suit individual applications. Different implementations of the join index are examined to determine how the join index can be efficiently maintained. To this end, we also conduct a number of experiments on intersection join and window queries, and the results confirm that semi-precomputation of join results is a robust and cost effective approach to join processing.
ISSN:0219-1377
0219-3116
DOI:10.1007/BF03325111