不确定数据流自适应并行连接算法及应用  

Self-Adaptive Concurrent Algorithm and Applications for Window Joins over Uncertain Data Streams

作　　者：钱江波[1] 王志杰[1] 陈华辉[1] 王海斌[2] 

机构地区：[1]宁波大学信息科学与工程学院,宁波315211 [2]宁波市公安局,宁波315040

出　　处：《电信科学》2012年第2期86-94,共9页Telecommunications Science

基　　金：国家自然科学基金资助项目(No.60803021;No.60973047);浙江省公益技术应用研究基金资助项目(No.2010C33149;No.2011C21076);浙江省自然科学基金资助项目(No.Y1091189);宁波市自然科学基金资助项目(No.2010A610115)

摘　　要：不确定数据流对处理过程有独特的需求,如存储空间有限、响应时间很短、需要连续处理、数据无限等,这对数据流的处理算法,特别是耗时、耗内存较多的连接操作提出了挑战。针对大规模不确定数据流并行连接所存在的速度较慢和内存消耗大的问题,提出了多核处理器上不确定数据流并行连接和内存溢出时自适应处理的一系列算法,能够高速在线处理并发不确定数据流。在此基础上,针对道路各个卡口监控到的不确定数据流,提出一种实时发现套牌车的方法。实验采用真实数据、均匀数据、高斯数据进行评估,证明算法具有良好的性能,其处理速度比内存数据库Timesten速度提高2~8倍,能够满足实时交通套牌车监控的需求。Recently there has witnessed emergence of uncertain data streams,with features of time-varying,uncertain,unpredictable and continuous,in many new application.The data process encounters many technical challenges,such as limited memory,very short response time,continuous processing and so on.Window join is one of the difficult problems as it cost many resources.Focusing on the problems on high-speed processing and memory overflow,a series of algorithms are proposed to tackle simultaneous window joins over large scale uncertain data streams.On this basis,an original application to monitor clone cars is presented.Experiments with real data,uniform data and Gaussian data show that the algorithms gain good performance,and its processing speeds faster than the memory database（Timesten） 2~8 times,to meet the requirements of monitoring clone cars in real traffic.

关 键 词：不确定数据流 窗口连接 内存溢出 并行计算 

分 类 号：TN959.73[电子电信—信号与信息处理]