【作者】 金澈清；

【导师】 周傲英；

【作者基本信息】 复旦大学 ， 软件与理论， 2005， 博士

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

【Abstract】 Data stream model has appeared in a growing number of information-processing applications in the last decade, such as internet, sensor networks, network traffic monitoring, network security, data mining, financial monitoring, manufacturing, chronometer and many more. Compared with traditional data models, data stream model owns several distinguishing characteristics, (l)the volume of a stream is unbounded, (2)the rate of stream is very rapid, (3)tuple’s arriving order cannot be controlled by applications, (4)each tuple can only be seen once, except that it is reserved for a special purpose.Because of features listed above, devising algorithms for querying and processing over data streams encounters following great challenges. At first, on seeing each new element in the data stream, stream algorithms are required to process it rapidly to update answers in real time. Secondly, compared to the volume of data stream seen so far, the main memory or disk storage that is available for computation is typically very small. Thirdly, for most problems, stream algorithms can only provide approximate answers, but with guaranteed precision in general. Finally, a good stream algorithm can still be efficient even when streams outside change a lot.Traditional data processing techniques can hardly be applied to process data streams directly. Despite the success in traditional applications, Database Management System(DBMS) is infeasible to process such data because DBMS can run a query only when all data are preloaded. Another traditional method, which is based on randomly accessing memory where all data are loaded, is also inapplicable for the volume of stream seen so far is greater than the memory size. This made researchers work out novel querying and processing techniques over data streams.In this paper, we have studied a few principal problems over data streams, and made several contributions.1. Mining frequent items over data streams is a basic problem over streams. We firstly propose a novel method, called hCount, which can estimate the fre-更多还原