科研之友
微信
新浪微博
Facebook
分享链接
摘要
过去十年中,数据流模型在一些信息处理应用中广泛出现,这些应用包括因特网、传感器网络、网络交通监控、计算机网络安全、数据挖掘、金融监控、制造业、天文等等。和传统数据模型相比,数据流模型具有几个截然不同的特征:(1)数据总量被假定为是无限的;(2)数据到达速率非常快;(3)数据到达次序不受应用所约束;(4)除非可以保存,每个元素均只能够“看”一次。针对数据流模型的查询处理技术具有几点特殊要求。首先,该技术必须能够快速处理每一个元组,实时输出查询处理结果。其次,该技术的空间复杂度要低,因为数据流的规模被假定为是无限的而内存是有限的。再次,这类技术由于空间复杂度低、处理元组速率高,往往只能够得到近似解,但一般而言,该近似解都具备一定的精确度。最后,该技术适应性要强。数据流在某些应用中可能非常不稳定,不仅数据分布,而且流速都可能发生剧烈变化,“好”的数据流查询处理技术必须能够在各种状况下都具备良好的性能。 传统的数据处理技术很难被应用到数据流模型中去。数据库管理系统(DBMS)需要先将所有数据保存起来,再提交查询进行处理,难以满足实时应用的需求。另外一种处理技术是首先将所有数据全部载入到内存中,以随机访问的方式解决应用问题。但是由于数据流数据量远大于主机内存,该技术也不现实。这个现状迫使研究人员深入研究数据流模型,设计新的查询处理技术。 本文针对数据流查询处理中的几个基本问题进行研究,并做出了以下几点贡献: 1.如何挖掘数据流上的频繁元素是数据流研究的一个基本问题。我们提出了hCount算法来解决这个问题。该算法仅需要e/ε·ln(-M/ln ρ)个计数器,就能够估算每个元素的值,且最大误差不超过ε。我们还将hCount算法和一个空间时间索引结构(sRB-树)相结合,提出了stFreq算法,用于在空间时间流上挖掘频繁元素。该方法空间复杂度低,查询精度高。 2.估算分位数(quantile)问题也是数据流上的一个基本问题。我们提出了一种新算法,该算法仅仅需要2elog~2 M/ε·ln(-M/ln ρ)个计数器,就能够在包
