论文部分内容阅读
随着互联网技术的发展和广泛应用,流动数据管理在各种应用系统中变得越来越重要.和传统的数据库管理系统不同,数据流管理系统以查询为中心,系统中预先注册有成千上万个持续查询;流动的数据源源不断的到达,一旦流过就不能再被访问.为了实时处理日益增长的注册查询和到达速度越来越快的流动数据,必须在注册的查询上建立索引,当一个数据流元组到达时,利用查询索引快速返回哪些查询得到了匹配.
本文提出了一种基于决策树的查询索引结构,我们称之为查询决策树.查询决策树不仅利用了查询内各个谓词间的合取关系,还充分利用了单个属性上的谓词索引,各种单属性上的谓词索引能够很容易集成到这种索引结构中.使用查询决策树索引,一个数据元组的最坏匹配时间为O(Mf(N)),其中M为属性个数,N为查询个数,f(N)为单属性谓词索引的搜索时间复杂度上界,对于常用的单属性谓词,一般有f(N)=o(log(N)).
在构造查询决策树时,如何选择划分属性,决定了查询决策树的平均匹配效率.本文将经典的ID3决策树构造算法引入到查询决策树的构造算法中,得到了基于信息增益的划分属性选择算法.由于没有考虑到达的数据流的属性值分布,信息增益法不能构造平均匹配效率最高的查询决策树.本文提出了一个递归的最优查询决策树构造算法,它使用一个刻画了数据流分布的数据元组集合做为训练样本集合.但这个算法本身复杂度太高,并不实用.本文提出了另外一个基于估计时间代价的划分属性选择算法,它用查询集合的大小来估计子树的匹配代价,而不是递归地构造最优查询子树,从而降低了查询决策树构造的时间复杂度.估计时间代价法不一定构造出最优查询决策树,本文的实验证明估计时间代价法构造的查询决策树平均匹配效率优于信息增益法构造的查询决策树,当查询集合较小时其平均匹配效率接近最优查询决策树.
数值区间谓词是最常用的单属性上的谓词,本文提出了一种组合区间索引结构.组合区间索引在属性值域区间端点密集的区域建立基于CEI的间接索引,然后在上层建立基于IBS-tree的间接区间索引.IBS-tree具有O(log(N))的搜索时间,消耗O(Nlog(N))的存储;CEI区间索引具有O(1)的搜索时间,但消耗大得多的存储.当区间端点较集中分布于某些子区间时,组合区间索引使用较少的存储,而搜索性能接近CEI.