一种数据流滑动窗口上的索引连接策略

摘要

近几年来,数据流的应用(DataStreamAppli-cation)变得越来越广泛.在数据流的应用中,传统的数据与查询模型已经不再适用.在传统的数据库应用中,数据是持久稳固的.通常,数据库中包含的是无序的静态数据集,这些数据的插入与删除操作相对于查询的插入与删除是很少的.用户可以随时加入查询来得到关心的结果.但在数据流中,数据是连续不断的、无界的、并且速度可能是变化的、以一种序列(流式)的形式在线到达的.一些典型的数据流应用如:传感器数据处理、在线拍卖、网络监控、入侵检测控制、电话呼叫记录以及股市信息分析等等.本文介绍了一种在滑动窗口上建立索引的方法,从而提高连接查询处理的效率.对滑动窗口进行划分,并在上面采用了红黑树建立索引,使得能够支持范围查询.由于是把元组的连接属性值作为索引的节点键值,相同的值会加入到一个节点上,因此当元组的连接属性值重复越多时索引会越显出优势.另外,本文中讨论都是以两个流的连接为例,如何将索引的方法扩展到多流连接和异步流连接是将来的工作.