论文部分内容阅读
现在各种网络数据、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查询算法中,并用实验验证。