基于M-tree的不等半径覆盖相异多样集求解方法  

Dissimilarity and Coverage Diversification with Different Radius based on M-tree

作　　者：刘明星[1] 马武彬[1] 邓苏[1] 黄宏斌[1] 

机构地区：[1]国防科学技术大学信息系统工程重点实验室,长沙410073

出　　处：《计算机研究与发展》2013年第S1期290-296,共7页Journal of Computer Research and Development

基　　金：国家"八六三"高技术研究发展计划基金项目(2011AA010106);国家自然科学基金项目(71071160)

摘　　要：通过查询结果多样化处理,能够显著提升用户查询体验.过去的研究集中在等半径结果集多样化的无向图求解,而首次研究不等半径下多样集的有向图求解方法.基于结果集的覆盖相异多样集定义及有向图描述,提出多样化结果集的启发算法,并基于M-tree索引结构实现算法的求解.为了提高算法执行效率,提出剪枝等策略.最后,通过实验,从多样化结果集的大小及计算代价两个方面对比分析验证文中提出算法,并得出相关结论.Diversification of search result can significantly enhance the user's query experience,while giving a comprehensive response to the whole information of the search result.Related works about result diversifying focused on computation of undirected graph with equal radius.To the best of our knowledge,this paper was the first one that contributed to the result diversification with different radius.A new,distance radius based dissimilarity and coverage diversity definitions and its directed graph based descriptions were proposed so that it could automatically allocate distance radius for the query object,and heuristics for its approximation were provided.In the end of this paper,efficient implementations of the algorithms based on the prune rule were presented,and experiments evaluating the performance demonstrated the efficiency of the algorithms in two aspects of the size of diverse subset and computational cost.

关 键 词：结果集多样化 不等半径 覆盖 相异 M-tree 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]