【作者】 崇志宏；

【导师】 周傲英；

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

【摘要】 与传统数据密集型应用相比，诸如网络监控系统等顺序产生的实时数据无法精确存储在数据库中，这种数据序列被称为数据流。数据流的典型特点是，其存储消耗具有潜在的无界性，其产生次序、间隔等统计特性具有不确定性，因此，数据流处理的算法需要具备以下的特点：1)算法复杂度必须是次线性的，输出结果可以是近似的；2)算法能够实时处理数据流输入。线性复杂度算法不能处理数据流的存储、查询和分析处理，因此，通过屏蔽或汇总数据流来控制次线性复杂度存储消耗成为数据流研究的重要内容。本篇论文通过对数据流上频繁项（集）发现、分布数据流并上聚合函数估算和κ-中值点（κ-median）搜寻，研究数据流处理的屏蔽和汇总的基本策略，主要贡献有：1．基于在线屏蔽策略，提出数据流上拒真的频繁项（集）发现，使用O(s^-1ln(2δ^-1)存储以至少1-δ概率输出频繁项；使用O(K／sln(s^-1δ^-1))存储可靠挖掘边界频繁项集（频繁项集的浓缩表示）；2．基于采样屏蔽策略，提出滤除分布数据流中的冗余和不一致的算法，应用min-wise哈希采样数据流而获取均匀样本集。由于获取的样本集不受分布流中冗余和不一致数据影响，能够准确估计聚合函数值，并进一步应用min—wise哈希方法采样位置流（location streams）来搜寻κ-中值点；3．基于汇总数据流策略，提出数据流上κ-中值点的快速估算算法，应用空间分割的汇总结构控制存储复杂度。不同于位置流中的频繁更新，数据流上κ-中值点需要单遍扫描庞大数目点集来获取近似中值点集。研究发现分割粒度不是影响κ-中值点近似程度的直接原因，避免精细分割产生指数增长的存储消耗问题。本文的研究成果可广泛应用于数据流相关的应用，如金融交易数据的处理、传感器网络数据的分析、以及网络实时监控等领域。更多还原

【Abstract】 Recently emerging data-intensive applications usually generate so called data streams in uncontrollable properties, coming order or interval for example while algorithms may consume almost infinite memory with respect to limited space available. Therefore, an algorithm for data streams is constrained to the following requirements: 1) it must run in sublinear space while its output may be approximate; 2) it can process inputs in an online way. Either shielding parts of data streams or summarizing data streams can be among alternative strategies for data streams processing when it can consume no more than sublinear space. In this thesis, we study several problems of data streams, including mining frequent item（set）s, estimating aggregation functions in distributed environments and searching k-median with the following contributions:1. Based on online shielding parts of data streams, we propose false negative algorithms for mining frequent item（set）s or maximal frequent itemsets. Using O(s^-1 ln(2δ^-1) memory, our algorithm can output frequent items with probability of at least 1-δ while capturing maximal frequent itemsets at the cost of O(（K/s） ln (s^-1δ^-1)).2. Based on sampling data streams, we propose algorithms for filtering out redundant and inconsistent data hidden in distributed data streams. Our algorithms can lead to uniform samples and approximate solutions to estimating such aggregate functions as average aggregate function and k-median.3. Based on summarizing data streams, we propose a time-efficient computation of k-median under memory constraints.In addition to data-intensive applications, our researches can be applied to computational geometry, massive graph, machine learning, pattern recognition and etc.更多还原