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

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

通过查询结果多样化处理,能够显著提升用户查询体验.过去的研究集中在等半径结果集多样化的无向图求解,而首次研究不等半径下多样集的有向图求解方法.基于结果集的覆盖相异多样集定义及有向图描述,提出多样化结果集的启发算法,并基于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.