An Indexed Non-Equijoin Algorithm Based on Sliding Windows over Data Streams

Processing a join over unbounded input streams requires unbounded memory, since every tuple in one infinite stream must be compared with every tuple in the other. In fact, most join queries over unbounded input streams are restricted to finite memory due to sliding window constraints. So far, non-in...

Full description

Saved in:
Bibliographic Details
Published in:Wuhan University journal of natural sciences 2006, Vol.11 (1), p.294-298
Main Authors: Yu, Ya-Xin, Yang, Xing-Hua, Yu, Ge, Wu, Shan-Shan
Format: Article
Language:English
Subjects:
数据流
滑动时窗
红-黑索引树
非等联结算法
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Processing a join over unbounded input streams requires unbounded memory, since every tuple in one infinite stream must be compared with every tuple in the other. In fact, most join queries over unbounded input streams are restricted to finite memory due to sliding window constraints. So far, non-indexed and indexed stream equijoin algorithms based on sliding windows have been proposed in many literatures. However, none of them takes non-equijoin into consideration. In many eases, non-equijoin queries occur frequently. Hence, it is worth to discuss how to process non-equijoin queries effectively and efficiently. In this paper, we propose an indexed join algorithm for supporting non-equijoin queries. The experimental results show that our indexed non-equijoin techniques are more efficient than those without index.
ISSN:1007-1202
1993-4998
DOI:10.1007/BF02831750