Multi-way R-tree joins using indirect predicates

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
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(저널논문)
  • Hit : 341
  • Download : 4
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0