论文部分内容阅读
Top-k查询技术广泛应用于各个领域,它根据用户自定义的打分函数找出打分函数值最高的前k个结果。然而,由于用户无法精确的定义打分函数,使得打分函数具有不确定性。并且针对多个用户提出相同的查询请求,Top-k查询返回相同的结果,使得Top-k查询技术很难应用于个性化查询中。然而,随着数据采集和管理技术的发展,人们发现了越来越多的不确定性数据,例如无线传感器网络、RFID系统、数据集成等等。不确定性数据逐渐得到了人们的关注,成为学术界的研究热点。在传统的确定性数据集上,Top-k查询具有确定的语义,仅需通过打分函数就能确定最终的查询结果。然而,不确定性数据集上的Top-k查询,需要综合考虑打分函数与对应属性值的概率。因此,传统的Top-k查询技术已经不能适用于不确定性数据集上。针对于此,学术界根据不同的应用场景定义了多种不同的Top-k查询语义,并在实际应用中取得了良好的效果。然而,学术界提出的各种不确定性Top-k查询语义仍然存在一些不足,主要表现在以下几点:(1)随着概率数据库中的互斥元组个数的增加,可能世界空间规模呈几何增长趋势,导致了计算量巨大,查询效率低下,甚至无法完成;(2)获得的查询结果并不完全满足用户的查询语义,用户的查询目标是实体,而传统的不确定性数据集上的Top-k查询语义返回的是元组,虽然元组在一定程度上也代表了实体集合,但并不全面;(3)传统的不确定性Top-k查询语义返回结果的概率太小,很难让用户信服。从上面的分析可以看出,传统的Top-k查询已经很难适用于一些个性化应用中,以及不确定性Top-k查询语义返回的结果存在的不足。本文针对上述问题,主要完成的工作有:首先,提出了个性化的Top-k查询语义,该查询语义可以根据用户的属性为用户定制查询结果。并提出相应的处理算法,算法的核心思想是分析用户属性集对数据集的影响程度,并利用卡方检验确定用户属性的影响程度,最后根据查询请求的用户的属性为用户定制查询结果。其次,本文针对元组级的U-Topk查询语义的上述不足,提出了一种新的面向实体的U-Topk查询语义及相应的查询处理算法。算法的基本思想是将元组级概率数据库转换为实体级概率数据库。在这个转换的过程中对某些满足合并条件的元组进行合并。面向实体的U-Topk查询算法,一方面可以极大地减少不确定性元组的个数;同时,可以查询结果也更能反映实体的整体状态,避免了元组级查询结果的片面性。文中对上述工作进行了详细的过程说明和算法描述,同时还使用来自于实际的真实数据集对所提算法的性能进行了实验验证。