| 摘要: |
| 查询结果重复率高是top-k查询处理过程中亟待解决的问题,已有的解决方法需要遍历初始结果集中所有的对象,因此,查询处理的效率较低.为了提高查询处理的效率,把初始结果集映射到欧氏空间中,根据拉式策略,可选用基于得分或基于距离两种方法之一从该空间选出差异最优子空间,在基于距离的方法中,对欧氏子空间进行分割并且利用探测位置和Voronoi图的几何特性减少二次查询对象的数目.在此基础上,提出了top-k查询结果有界多样化算法,并证明了算法的正确性.实验结果表明,所提出的算法提高了top-k查询处理效率. |
| 关键词: top-k查询 有界多样性 欧氏空间 拉式策略 Voronoi图 |
| DOI： |
| 分类号: |
| 基金项目:国家自然科学基金(61070032) |
|
| Bounded Diversification Methods for Top-k Query Results |
|
ZHOU Yu1, ZHAO Wei2,3, LIU Guo-Hua1, YUN Hui1, ZHAI Hong-Min1, WAN Xiao-Mei1
|
|
1.School of Computer Science and Technology, Donghua University, Shanghai 201620, China;2.State Grid Corporation of China Heilongjiang Electric Power Company Ltd. Information &3.Telecommunication Branch, Harbin 150000, China
|
| Abstract: |
| High repetition rate of query results is a problem needing a prompt solution in top-k query processing. Existing solutions require the traversing over all objects in initial result set which may cause a lower efficiency in query processing. To address the issue, this paper first maps initial result set to the Euclidean space and selects the optimal subspace using either the score-based method or distance-based method by adopting the pulling strategy. Applying the distance-based method, the Euclidean space is partitioned and the number of second query objects is reduced by incorporating geometric properties of Voronoi diagram. Further, the bounded diversification algorithm over top-k query results is developed and the soundness of the algorithm is proved. Experimental results demonstrate that the proposed algorithm improves the efficiency of top-k query processing. |
| Key words: top-k query bounded diversification Euclidean space pulling strategy Voronoi diagram |
