论文部分内容阅读
随着信息技术的飞速发展，许多应用领域均出现了一种称之为数据流的新型数据。与传统数据形式不同，数据流的特点是数据源源不断地产生，数据生成及传输的速度极快，并且数据分布未知。在应用中，人们需要对数据流进行实时地监测、查询和分析，以便及时准确地作出决策。传统的数据管理技术无法有效支持数据流上的查询处理，需要研究新的适合于数据流的查询处理技术。 本文研究数据流查询处理问题。针对各种常用的数据流查询类型，提出了相应的查询处理方法。研究内容包括数据流滑动窗口查询处理、数据流频繁项查询处理、多维数据流相似性查询处理、数据流隐私保护处理以及数据流查询处理原型系统。 本文的主要研究成果有以下几个方面。 (1)在滑动窗口查询处理方面，提出了更具一般性的γ粒度更新滑动窗口的概念，针对γ粒度更新滑动窗口查询，提出了三种连接查询实现算法和一种聚集查询实现算法，理论分析和实验结果表明这些算法具有很高的性能和效率。针对滑动窗口连接聚集查询，在分析了两种操作相关性的基础上，提出了IC和TC算法，使得查询处理的空间复杂度和时间复杂度均由O(N2)降为O(N)，这里N为滑动窗口的势。IC和TC算法具有很强的可扩展性，能够处理各种复杂的滑动窗口连接聚集查询。提出了滑动窗口查询的并行处理框架，给出了滑动窗口查询操作的并行实现算法、查询处理算法以及在线的查询优化方法。滑动窗口查询的并行处理方法使得查询能够在数据流流速极快以及滑动窗口规模宏大的情况下，仍能正确地进行处理。 (2)在数据流频繁项查询处理方面，提出了EC算法来计算数据流∈近似频繁项。EC算法的空间复杂度为O(1/∈)，平均每个数据项的处理时间为O(1)，输出结果频率的最大误差为∈(1-s+∈)N，其中s为用户给定的支持度，N为数据流目前为止到来的元组个数。与目前已有的同类算法相比，EC算法最优。 (3)在多维数据流相似性查询处理方面，提出一种基于压缩结构CV的查询处理算法CVNN，与基于随机抽样的处理方法相比，CVNN算法返回结果的准确率更高并且速度更快。 (4)针对数据流个体隐私保护问题，提出了一种新的隐私保护性质(k+,l)?anonymity，其隐私保护的能力要强于目前的k?anonymity和l?diversity等性质。给出了KLAST算法来实现数据流上的δ?constraint(k+,l)?anonymity。理论分析和实验结果表明，KLAST有效地实现了数据流的隐私保护。 基于上述基础研究结果，本文作者设计实现了数据流查询处理原型系统HIT-PDS。HIT-PDS是一个并行查询处理系统，拥有很强的数据流查询处理能力和良好的可扩展性。HIT-PDS验证了本文所提算法的正确性和有效性。