O2iJoin： An Efficient Index-Based Algorithm for Overlap Interval Join
O2iJoin： An Efficient Index-Based Algorithm for Overlap Interval Join作者机构：School of Computer Science and Technology Harbin Institute of Technology Harbin 150001 China Guangdong Key Laboratory of Popular High Performance Computers Key Laboratory of Service Computing and Application Shenzhen 518000 China
出 版 物：《Journal of Computer Science & Technology》 (计算机科学技术学报（英文版）)
年 卷 期：2018年第33卷第5期
页 面：1023-1038页
核心收录：
学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）]
基 金：supported by the National Key Research and Development Program of China
主 题：overlap interval join temporal relation overlap inverted index join algorithm
摘 要：Time intervals are often associated with tuples to represent their valid time in temporal relations, where overlap join is crucial for various kinds of queries. Many existing overlap join algorithms use indices based on tree structures such as quad-tree, B＋-tree and interval tree. These algorithms usually have high CPU cost since deep path traversals are unavoidable, which makes them not so competitive as data-partition or plane-sweep based algorithms. This paper proposes an efficient overlap join algorithm based on a new two-layer flat index named as Overlap Interval Inverted Index （i.e., O2i Index）. It uses an array to record the end points of intervals and approximates the nesting structures of intervals via two functions in the first layer, and the second layer uses inverted lists to trace all intervals satisfying the approximated nesting structures. With the help of the new index, the join algorithm only visits the must-be-scanned lists and skips all others. Analyses and experiments on both real and synthetic datasets show that the proposed algorithm is as competitive as the state-of-the-art algorithms.
维普期刊数据库