Multi-way R-tree joins using indirect predicates

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 403
  • Download : 23
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.
Publisher
ELSEVIER SCIENCE BV
Issue Date
2004-09
Language
ENG
Article Type
Article
Keywords

SPATIAL JOINS

Citation

INFORMATION AND SOFTWARE TECHNOLOGY, v.46, no.11, pp.739 - 751

ISSN
0950-5849
URI
http://hdl.handle.net/10203/1922
Appears in Collection
NE-Journal Papers(저널논문)

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0