基于极小独立支配集的多样化排序算法

Diverse Ranking Algorithm Based on Minimal Independent Dominating Set

为了满足用户的多元化需求和提高用户查询的满意度,出现了多样化排序算法的研究,但是目前多样化排序算法在多样化和相关性之间不能达到很好的平衡,且查询处理效率不能完全适应实际的交互需求,为此提出了一种基于极小独立支配集的多样化排序算法。将多样化子集选取问题转化为无向加权图的极小独立支配集的求解问题,以此兼顾查询结果的多样化和相关性;在求解过程中通过引入抛弃子集的概念来减少冗余顶点对之间距离的比较,加快算法求解的速度。仿真实验表明,所提算法在多样化性能和查询处理效率方面有一定的提升。

In order to meet the diversified needs and improve the satisfaction of user＇s query,the research of the diverse ranking algorithm has been developed.However,the current diverse ranking algorithm cannot achieve good balance between diversification and relevance,and the efficiency of query processing cannot fully meet the actual needs of the interaction.Thus,a new diverse ranking algorithm based on minimal independent dominating set（MIDS-DR）was proposed.First,the problem of selecting diversified subset is transformed into the minimal independent dominating set of the undirected weighted graph,so as to balance the diversification and relevance of query results.To speed up the algorithm,the concept of abandoned subset is introduced to reduce the comparison of distances between redundant vertex pairs during the solving process.The simulation results show that the proposed algorithm can improve the performance and query efficiency.