不确定数据集上ToP-k查询及优化算法的研究

摘要

Top-k查询技术应用广泛，其目标是根据用户自定义的打分函数找出数据集中评价最高的k个结果。在传统的确定性数据库中，Top-k查询具有明确的语义，学术界也已经提出了多种有效的查询优化方法。然而，随着数据采集和处理技术的不断发展，越来越多的应用领域发现了不确定性数据，如无线传感器网络、RFID系统、移动计算等等。不确定性数据逐渐得到了人们的关注，成为了学术界的研究热点。
　　在传统数据库中，Top-k查询的结果仅仅依靠打分函数值来排序，而基于不确定性数据集上的Top-k查询处理，需要综合考虑打分函数值及其取值概率。因此，传统Top-k查询技术不能直接应用于不确定性数据集上。以往的研究，针对不同的应用背景，已经提出了多种不确定数据集上的Top-k查询语义，然而针对特定语义不确定性Top-k查询处理问题依然是学术界面临的巨大挑战。另外，现有的不确定性数据管理和Top-k查询技术多是针对集中式数据库或数据流，而不确定性数据多来自于分布式系统，典型地如无线传感器网络、P2P系统等等。如果将集中式Top-k查询处理技术简单地移植到分布式存储的不确定数据集上，那么首先就需要从分布节点上收集所有的数据到中心节点，然后完成最终查询，将给系统带来巨大的通信开销、存储代价、及时间延迟。实际上，Top-k查询具有显著的特点:查询结果仅占全体数据集的极小部分。在某些系统中，节点资源非常有限，采用上述的集中式查询处理算法，也会造成巨大的不必要的节点资源损失。
　　从上面的分析可以看出，集中式不确定性数据集上的Top-k查询，以及分布式环境下的不确定性数据的Top-k查询，无论从查询语义和查询优化技术上都亟待进一步研究和解决。本文即针对上述问题展开研究，主要完成的工作有:
　　首先，提出了确定U-Topk最小范围查询的MSS4U-Topk算法，通过缩减U-Topk查询的数据集，可以大幅度地减少可能世界模型规模。另外，将MSS4U-Topk算法作为U-Topk查询处理的预处理过程，可以确定U-Topk查询必须扫描的元组范围，进而确定需遍历的可能世界模型空间规模，这为U-Topk查询处理算法的选择提供了重要依据。
　　其次，针对属性级不确定性提出了U-Topk查询优化算法APT4U-Topk。提出了可能世界模型概率阀值的概念，当计算的可能世界模型概率等于阀值时，可以确定后续可能世界模型概率皆小于阀值，终止算法，从而实现快速找出U-Topk查询结果的目标。通过实验，可以看出APT4U-Topk算法有效的提高了U-Topk查询效率。进一步将APT4U-Topk算法应用到分布式环境中，提出了DAPT4UTop-k算法。DAPT4U-Topk算法避免了节点端发送全部本地元组，有效地减少分布式系统中的通信开销。但是，在某些数据集情况下，节点依然需要上传大部分数据，DAPT4U-Topk算法的通信代价和时间复杂度依然较高。
　　针对在某些数据集上U-Topk查询需要展开全部可能世界模型，查询优化算法失效的情况，论文在最后一个部分提出了MPUTop-k查询优化算法。MPUTop-k的语义是返回概率最大的可能世界模型实例的Top-k向量。因为MPUTop-k不需要计算全部可能世界模型概率，因此更具有实际应用价值。进一步，我们将MPUTop-k查询优化算法应用到分布式环境中，提出了DMPUTop-k算法。由于全局MPUTop-k算法和各个结点局部MPUTop-k算法的返回的结果相同，因此DMPUTop-k算法可应用于多跳地分布式环境中。特别地，文中证明了如果可能世界模型空间中某个实例的概率不小于0.5时，从查询结果的角度来看，MPUTop-k和U-Topk查询是等价的。这个结论为U-Topk查询处理提供了一种近似计算的方法。
　　文中对上述工作进行了详细的过程说明和算法描述，包括必要的理论证明用以说明算法的正确性，同时还使用来自于生产实际的真实数据集和部分模拟数据集对所提算法的性能进行了实验验证。

目录

声明

摘要

第1章 引言

1．1 课题的研究背景及意义

1．2 国内外研究现状

1．3 本文主要工作

1．4 本文组织结构

第2章 相关工作

2．1 不确定性数据概述

2．1．1 不确定性数据产生原因

2．1．2 不确定性数据库组成

2．1．3 不确定性数据主要应用

2．2 不确定性数据管理技术

2．3 可能世界模型

2．4 不确定性Top-k查询语义研究

2．4．1 不确定性Top-k查询的研究内容

2．4．2 不确定性Top-k的查询语义

2．4．3 集中式不确定性Top-k排序标准

2．4．4 集中式不确定性Top-k的查询处理

2．5 分布式不确定性Top-k查询

第3章 集中式不确定性数据U-Topk查询优化

3．1 引言

3．2 确定U-Topk查询处理的最小扫描范围

3．2．1 问题定义

3．2．2 MSS4U-Topk查询算法过程

3．2．3 Quick MSS4U-Topk算法

3．2．4 实验与性能分析

3．3 属性级不确定性数据U-Topk查询算法优化

3．3．1 问题描述

3．3．2 U-Topk查询优化算法APT4-Topk算法过程

3．3．3 实验与性能分析

3．4 本章小结

第4章 分布式不确定性数据Top-k查询优化

4．1 引言

4．2 分布式不确定性数据U-Topk查询算法优化

4．2．1 问题定义

4．2．2 分布式不确定性数据U-Topk算法DAPT4U-Topk过程

4．2．3 实验与性能分析

4．3 分布式不确定性数据DMPU-Topk算法

4．3．1 最大可能Top-k查询

4．3．2 DMPU-Topk算法过程

4．3．3 实验与性能分析

4．4 本章小结

第5章 结论

5．1 本文工作总结

5．2 进一步研究的工作

参考文献

致谢

攻读硕士期间发表的论文及参加的项目