2018-世界科学-查询和挖掘不确定的数据流-165页_11mb

《Querying and Mining Uncertain Data Streams》总结

核心内容

本书《Querying and Mining Uncertain Data Streams》聚焦于不确定数据流的查询与挖掘问题，探讨了如何在数据流的不确定性和时间敏感性背景下，设计高效、准确的数据处理方法。数据流通常具有大容量、高速度和多样性，而不确定数据流则进一步引入了数据的不精确性，包括属性级不确定性和存在级不确定性。书中提出了多种数据处理模型与方法，以应对这些挑战。

主要观点

• 不确定数据流的定义：数据流中的每个元组可能包含多个可能值，其存在性或属性值的准确性可能不确定。这种不确定性来源于低质量硬件、人工干预、数据缺失和数据集成等因素。
• 数据模型：采用可能世界语义（Possible World Semantics）来建模不确定数据流，其中每个可能世界代表一组确定值的组合，与相应的概率相关联。对于不确定数据流，可能世界数量会指数级增长，这给处理带来了巨大挑战。
• 查询模型分类：
  • Landmark模型：考虑从固定时间点到当前的所有元组。
  • Time-decay模型：元组的权重随时间衰减，常用于统计聚合。
  • Sliding-window模型：仅考虑预定义时间窗口内的元组，超出窗口的元组被过滤。
• 关键研究问题：
  • Top-k查询：在不确定数据流中，如何高效地处理Top-k查询，尤其是在滑动窗口模型下。
  • ER-Topk查询：基于期望排名的Top-k查询，通过构建DomGraph、probTree和ES缓冲区等结构实现。
  • 稀有度估计（Rarity Estimation）：用于检测不确定数据流中异常事件，提出了精确和近似两种计算方法。
  • 集合相似性（Set Similarity）：在可能世界语义下，定义了两种集合相似性度量方式，支持精确和近似计算。
  • 聚类（Clustering）：提出了一种新的数据结构“Uncertain Feature (UF)”，用于总结不确定数据流，并改进了传统流式聚类算法。

关键信息

1. Top-k 查询

• 本书提出了一种统一框架，用于处理滑动窗口模型下的Top-k查询。
• 框架内嵌多种Top-k定义，支持在有限空间内高效处理。
• 通过紧凑集合（Compact Set）等结构，减少存储开销，同时保持查询效率。
• 实验结果显示该框架在时间和空间上均优于传统方法。

2. ER-Topk 查询

• ER-Topk查询基于期望排名，用于对不确定数据流中的元组进行排序。
• 构建了三个结构：DomGraph（存储候选元组）、probTree（用于计算精确期望排名）、ES缓冲区（用于计算近似期望排名）。
• 该方法能够有效处理动态数据流中的排名变化问题。

3. 稀有度估计

• 稀有度用于衡量在不确定数据中，具有相同频率的元素比例。
• 提出了精确计算方法（使用动态规划，时间复杂度为O(m³)）和近似方法（基于蒙特卡洛技术，空间和时间效率高）。
• 通过启发式规则，可以仅计算部分稀有度值，而无需计算全部。

4. 集合相似性

• 集合相似性用于衡量两个概率集合之间的相似性，特别适用于存在噪声或数据汇总的应用场景。
• 定义了两种相似性度量：一种用于精确计算，另一种基于采样实现近似计算。
• 提出了一个流式处理方法，能够在处理大规模概率集合时保持高效。

5. 聚类

• 提出了一种新的数据结构“Uncertain Feature (UF)”，用于总结不确定数据流。
• 改进了传统流式聚类方法（如CluStream和UMicro），提出了一种新的算法cluUS，其性能优于现有方法。
• 该方法在滑动窗口模型下表现尤为突出，能够有效应对元组过期问题。

结构清晰

• 章节安排：本书共分为7章，涵盖从引言到结论的完整内容。
• 附录信息：包括参考文献、索引、作者介绍等。
• 实验验证：各章节均附有实验结果，验证所提方法的效率与准确性。

作者信息

• Cheqing Jin：东华师范大学软件工程学院教授，研究方向包括流数据管理、不确定数据管理等。
• Aoying Zhou：东华师范大学软件工程学院教授，兼任数据科学与工程研究所所长，研究兴趣包括大数据管理、数据库性能优化等。

总结

本书系统性地探讨了不确定数据流的查询与挖掘技术，提出了多种高效的数据处理模型与算法。其重点在于如何在不确定性和时间敏感性的约束下，实现空间与时间效率的平衡。书中不仅涵盖了理论模型的构建，还通过实验验证了所提方法的有效性，为不确定数据流的处理提供了重要的理论与实践指导。