Multi-way R-tree joins using indirect predicates

doi:10.1016/j.infsof.2003.12.007

Multi-way R-tree joins using indirect predicates

2004-09-01

1

PRE

AI

DOI：10.1016/j.infsof.2003.12.007

Original

Original request for help

Save

Abstract

En 中文

Since spatial join processing consumes much time, several algorithms have been proposed to improve spatial join performance. Spatial join has been processed in two steps, called filter step and refinement step. The M-way R-tree join (MRJ) is a filter step join algorithm, which synchronously traverses M R-trees. In this paper, we introduce indirect predicates which do not directly come from the multi-way join conditions but are indirectly derived from them. By applying indirect predicates as well as direct predicates to MRJ, we can quickly remove the minimum bounding rectangle (MBR) combinations which do not satisfy the direct predicates or the indirect predicates at the parent level. Hence we can reduce the intermediate MBR combinations for the input to the child level processing and improve the performance of MRJ. We call such a multi-way R-tree join algorithm using indirect predicates indirect predicate filtering (IPF). Through experiments using synthetic data and real data, we show that IPF significantly improves the performance of MRJ. (C) 2004 Elsevier B.V. All rights reserved.

Keywords:

spatial databases

spatial join

M-way R-tree join

indirect predicates

Multi-way R-tree joins using indirect predicates

Abstract

AI Summary

Journal

Organization