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