(东华大学 计算机科学与技术学院, 上海 201620;国网黑龙江省电力有限公司信息通信公司, 黑龙江 哈尔滨 150000)
Bounded Diversification Methods for Top-k Query Results
ZHOU Yu,ZHAO Wei,LIU Guo-Hua,YUN Hui,ZHAI Hong-Min,WAN Xiao-Mei
(School of Computer Science and Technology, Donghua University, Shanghai 201620, China;State Grid Corporation of China Heilongjiang Electric Power Company Ltd. Information & Telecommunication Branch, Harbin 150000, China)
Chart / table
Similar Articles
Article :Browse 1196   Download 1530
Received:May 07, 2014    Revised:August 19, 2014
> 中文摘要: 查询结果重复率高是top-k查询处理过程中亟待解决的问题,已有的解决方法需要遍历初始结果集中所有的对象,因此,查询处理的效率较低.为了提高查询处理的效率,把初始结果集映射到欧氏空间中,根据拉式策略,可选用基于得分或基于距离两种方法之一从该空间选出差异最优子空间,在基于距离的方法中,对欧氏子空间进行分割并且利用探测位置和Voronoi图的几何特性减少二次查询对象的数目.在此基础上,提出了top-k查询结果有界多样化算法,并证明了算法的正确性.实验结果表明,所提出的算法提高了top-k查询处理效率.
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.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(61070032) 国家自然科学基金(61070032)
Foundation items:
Reference text:


ZHOU Yu,ZHAO Wei,LIU Guo-Hua,YUN Hui,ZHAI Hong-Min,WAN Xiao-Mei.Bounded Diversification Methods for Top-k Query Results.Journal of Software,2014,25(S2):136-146