Partitioned-Tree Nested Loop Join: An Efficient Join for Spatio-Temporal Interval Join

Jinsoo LEE; Wook-Shin HAN; Jaewha KIM; Jeong-Hoon LEE

doi:10.1587/transinf.E96.D.1206

Partitioned-Tree Nested Loop Join: An Efficient Join for Spatio-Temporal Interval Join

Jinsoo LEE, Wook-Shin HAN, Jaewha KIM, Jeong-Hoon LEE

Full Text Views

0

Share
Cite this

Summary :

A predictive spatio-temporal interval join finds all pairs of moving objects satisfying a join condition on future time interval and space. In this paper, we propose a method called PTJoin. PTJoin partitions the inner index into small sub-trees and performs the join process for each sub-tree to reduce the number of disk page accesses for each window search. Furthermore, to reduce the number of pages accessed by consecutive window searches, we partition the index so that overlapping index pages do not belong to the same partition. Our experiments show that PTJoin reduces the number of page accesses by up to an order of magnitude compared to Interval_STJoin [9], which is the state-of-the-art solution, when the buffer size is small.

Publication: IEICE TRANSACTIONS on Information Vol.E96-D No.5 pp.1206-1210

Publication Date: 2013/05/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.E96.D.1206

Type of Manuscript: LETTER

Category: Data Engineering, Web Information Systems

Cite this

Copy

Jinsoo LEE, Wook-Shin HAN, Jaewha KIM, Jeong-Hoon LEE, "Partitioned-Tree Nested Loop Join: An Efficient Join for Spatio-Temporal Interval Join" in IEICE TRANSACTIONS on Information, vol. E96-D, no. 5, pp. 1206-1210, May 2013, doi: 10.1587/transinf.E96.D.1206.
Abstract: A predictive spatio-temporal interval join finds all pairs of moving objects satisfying a join condition on future time interval and space. In this paper, we propose a method called PTJoin. PTJoin partitions the inner index into small sub-trees and performs the join process for each sub-tree to reduce the number of disk page accesses for each window search. Furthermore, to reduce the number of pages accessed by consecutive window searches, we partition the index so that overlapping index pages do not belong to the same partition. Our experiments show that PTJoin reduces the number of page accesses by up to an order of magnitude compared to Interval_STJoin [9], which is the state-of-the-art solution, when the buffer size is small.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.E96.D.1206/_p

Copy

@ARTICLE{e96-d_5_1206,
author={Jinsoo LEE, Wook-Shin HAN, Jaewha KIM, Jeong-Hoon LEE, },
journal={IEICE TRANSACTIONS on Information},
title={Partitioned-Tree Nested Loop Join: An Efficient Join for Spatio-Temporal Interval Join},
year={2013},
volume={E96-D},
number={5},
pages={1206-1210},
abstract={A predictive spatio-temporal interval join finds all pairs of moving objects satisfying a join condition on future time interval and space. In this paper, we propose a method called PTJoin. PTJoin partitions the inner index into small sub-trees and performs the join process for each sub-tree to reduce the number of disk page accesses for each window search. Furthermore, to reduce the number of pages accessed by consecutive window searches, we partition the index so that overlapping index pages do not belong to the same partition. Our experiments show that PTJoin reduces the number of page accesses by up to an order of magnitude compared to Interval_STJoin [9], which is the state-of-the-art solution, when the buffer size is small.},
keywords={},
doi={10.1587/transinf.E96.D.1206},
ISSN={1745-1361},
month={May},}

Copy

TY - JOUR
TI - Partitioned-Tree Nested Loop Join: An Efficient Join for Spatio-Temporal Interval Join
T2 - IEICE TRANSACTIONS on Information
SP - 1206
EP - 1210
AU - Jinsoo LEE
AU - Wook-Shin HAN
AU - Jaewha KIM
AU - Jeong-Hoon LEE
PY - 2013
DO - 10.1587/transinf.E96.D.1206
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E96-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 2013
AB - A predictive spatio-temporal interval join finds all pairs of moving objects satisfying a join condition on future time interval and space. In this paper, we propose a method called PTJoin. PTJoin partitions the inner index into small sub-trees and performs the join process for each sub-tree to reduce the number of disk page accesses for each window search. Furthermore, to reduce the number of pages accessed by consecutive window searches, we partition the index so that overlapping index pages do not belong to the same partition. Our experiments show that PTJoin reduces the number of page accesses by up to an order of magnitude compared to Interval_STJoin [9], which is the state-of-the-art solution, when the buffer size is small.
ER -