目录
摘要............................................................................................................................... IV Abstract ............................................................................................................................V 第一章绪论 .. (1)
1.1 研究背景意义 (1)
1.2 国内外研究现况 (3)
1.3 本文结构安排 (8)
第二章不确定数据Top-k (10)
2.1 可能世界语义下的概率数据库模型 (10)
2.2 不确定数据Top-k查询 (13)
第三章E-Score排序语义改进及算法研究 (18)
3.1 E-Score语义 (18)
3.2 不确定数据元组的位置及位置概率 (19)
3.3 PPE-Score语义思想及算法 (20)
第四章PP-Pruning剪枝技术 (23)
4.1 PP-Pruning算法 (23)
4.2 PP-Pruning剪枝技术在其它Top-k排序算法中的应用 (23)
第五章云环境下的不确定数据Top-k查询 (26)
5.1 云环境和云计算介绍 (26)
5.2 开源的Hadoop框架 (27)
5.3 云平台下的Top-k查询技术 (31)
第六章实验验证与结果分析 (33)
6.1 单机环境实验验证 (33)
6.2 云平台实验验证 (35)
6.3 本章小结 (40)
第七章总结与展望 (41)
7.1 现有工作总结 (41)
7.2 未来研究展望 (41)
参考文献 (43)
攻读硕士期间发表论文及参与的科研项目 (47)
致谢 (48)
学位论文原创性声明和关于学位论文使用的授权声明 (49)
摘要
现在各种网络数据、GPS数据、传感器数据等大量涌现于日常生活之中。由于数据的记录和传输方面存在的问题，这些数据一般都存在噪声、数据丢失、测量不精确或不完整等现象，因此大数据往往也伴随着不确定性。现在越来越多的场合急需处理这种类型的不确定数据。由于数据来源范围广，数据量大等原因，大数据往往价值密度很低，对人们真正有用的数据却是小部分数据。然而，用户往往只关心符合自己需求的少部分数据，因此至关重要的是如何快速获得自己需要的那部分数据。从而对不确定数据的排序、检索成为了当今课题研究热点。
高效的Top-k查询返回的是最能满足用户查询条件的k个结果，越来越受到研究者的重视。不确定数据的查询排序问题，其实就是首先确定一个特定意义的排序语义规则，然后根据此语义规则形成相应的算法，最后用这个算法对不确定数据进行Top-k查询排序从而得到相应的Top-k排序结果。
元组的属性值和概率是不确定数据的两个基本属性，也是Top-k排序语义规则生成的依据，分值与概率的平衡问题一直是不确定性数据Top-k查询的焦点问题。最近几年，学者们也基于自己的偏好或需求，采用不同的分值和概率平衡方式提出相应的Top-k查询语义和算法。最经典语义有：U-topK, PT-k, E-Score Rank ，PRF等。这些Top-k查询都是基于特定场景和特定需求生成的，一种查询语义一般只适合一种用户查询偏好。Li 采用Kendall 距离对同一数据集上不同Top-k查询语义得到的Top-k排序结果进行比较,发现结果差异显著。Li等人进一步提出了一种综合的参数化排序语义函数PRF。
Top-k查询语义不但没有很好的普遍适应性，而且一些Top-k查询语义还存在缺点与不足，有待提高和完善。另外，现有Top-k排序算法最好也只是多项式时间复杂度的，这样的算法在应对更大规模数据挑战时显得力不从心，因此不确定数据Top-k查询算法也急需改进与提高。
针对以上问题，本文做了一些相关研究，本文的主要贡献如下：
第一：运用新的迭代思想和迭代函数，利用Java编程语言实现位置概率迭代算法。
第二：改进了E-Score语义，提出新的Top-k查询语义PPE-Score查询语义，并且提出相应的算法。
第三：提出了新型的基于位置概率的剪枝技术PP-Pruning剪枝技术，并把PP-Pruning 剪枝技术运用到其它Top-k查询算法中，并用实验验证。
关键词：不确定数据，Top-k查询，位置概率，排序算法