H-Tree:一种面向大数据流在线监测的层次索引  

H-Tree:Hierarchy Index for Online Monitoring of Big Data Streams

作　　者：臧文羽[1,2] 李军[1,3] 方滨兴[1,2,3] 谭建龙[2] 

机构地区：[1]中国科学院计算技术研究所信息安全研究中心,北京100190 [2]中国科学院信息工程研究所信息内容安全技术国家工程实验室,北京100093 [3]北京邮电大学计算机学院,北京100876

出　　处：《计算机学报》2015年第1期35-44,共10页Chinese Journal of Computers

基　　金：国家自然科学基金(61370025);国家"八六三"高技术研究发展计划(2011AA010703;2012AA012502);国家"九七三"重点基础研究发展规划项目基金(2013CB329606);中国科学院战略性先导科技专项课题(XDA06030200)资助~~

摘　　要：随着计算机网络的迅猛发展和大数据时代的到来,数据越来越频繁地呈现出多属性异构的特点.这种包含多种不同类型属性的大数据流称为异构大数据流(Heterogeneous Big Data Streams).在面向大规模数据在线监测分析的应用中,通常需要在异构大数据流上注册大规模监测规则.因此,对于每一个数据流元组,必须用最小的计算开销满足所有的规则.同时,由于大数据流上监测规则集异常庞大,提高规则监测的性能是大规模数据流在线监测的关键.基于此,该文提出一种层次化的索引结构H-Tree及其在线规则匹配算法.具体的,H-Tree将大数据流上的属性集划分为离散型属性和连续型属性.基于不同的属性集,构建两层索引结构:在第1层,通过改进的红黑树对离散型谓词构建触发索引;在第2层,通过量化连续型谓词构建多维索引结构.H-Tree的在线规则匹配算法利用关联关系表对两层索引的监测结果进行融合过滤.实验分析表明,与经典的R+方法相比较,H-Tree通过层次化的索引结构,在不降低准确度的前提下,显著提升了大数据流的监测效率.With the evolution of computer network and the coming of big data era,data stream presents new characters of multiple attributes and heterogeneous.We name the streams that contain multiple attributes Heterogeneous Big Data Streams.In the big date stream oriented online monitoring systems,there usually exist many filtering queries that specify the filtering objectives.Thus,for every incoming tuple,it should satisfied all queries with the least computational cost.Meanwhile due to the huge amount of filtering queries on big data streams,a key problem in such a filtering scenario is how to index the query set to make the detection of heterogeneous big data streams more efficiency.Based on this problem,we propose a hierarchal index framework（H-Tree）and its online matching algorithms.Specifically,H-Tree clusters the attributes into discrete attributes and continuous attributes,which executes a two-stage indexing strategy.In the first stage,H-Tree builds indexes according to the discrete predicates.In the secondstage,H-Tree build multi-dimension index based on the continuous predicates.Experiments demonstrate that H-Tree greatly improve efficiency on big data streams monitoring without losing accuracy compared with R＋solution.

关 键 词：异构大数据流 监测规则 索引 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]