作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2006, Vol. 32 ›› Issue (21): 41-43. doi: 10.3969/j.issn.1000-3428.2006.21.015

• 博士论文 • 上一篇    下一篇

分布式数据流连接查询算法

刘学军1,2,钱江波2   

  1. (1. 南京工业大学信息科学与工程学院,南京210009;2. 东南大学计算机科学与技术系,南京 210096)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2006-11-05 发布日期:2006-11-05

Algorithms for Sliding Window Join over Distributed Data Stream

LIU Xuejun1,2, QIAN Jiangbo2   

  1. (1. College of Information Science and Engineering, Nanjing University of Technology, Nanjing 210009; 2. Department of Computer Science and Technology, Southeast University, Nanjing 210096)
  • Received:1900-01-01 Revised:1900-01-01 Online:2006-11-05 Published:2006-11-05

摘要: 分布式处理是数据流管理系统发展的必然趋势。文章研究了分布式数据流的连接查询,提出DM3Join算法,它由2部分组成:一是通过分解并发的连接请求,合并相同的连接谓词,形成分布式查询操作算子;二是数据流在各分布式代理(Agent)中流转实现部分连接,并在查询引擎处组合成最终结果。DM3Join算法采用了一种类似路由表的结构执行窗口连接,由于可以共享中间结果,算法只需扫描数据1遍。分析和实验证明,该连接算法是高效的。

关键词: 数据流, 窗口连接, 连续查询, 分布式系统

Abstract: Distributed processing is a very promising route towards a more effective and adaptive data stream processing model. This paper studies window join over data streams, which is an important class of continuous operators for distributed processing. A novel distributed join approach named DM3Join is proposed. DM3Join consists of two parts. One is to decompose concurrent join query, merge the same join predicate and form distributed join operator. The other is to implement part join based on moving of data stream through distributed agent, and form final results in query engine. Different from most of other algorithms, the algorithm executes window joins performs like a router and needs only one scan over the data streams since different join queries share the intermediate results. The experimental results show that the algorithm is effective.

Key words: Data streams, Window join, Continuous queries, Distributed system

中图分类号: