In this paper, we combine query result diversity with query relaxation to balance the result number and result quality. Relaxation guarantees the number of the que-ry results, returning more relevance elements to the query if the results are too few, while the diversity tries to reduce the similarity among the returned results. By making a trade-off of similarity and diversity, we improve user experience. To achieve this goal, we design the goal function combining similarity and diversity. Aiming at this goal, we propose three algorithms. Among them, algorithms gen-Greedy and genCluster perform relaxation first and select part of the candidates to diversify. Pre-analysis of the dataset is made to choose a proper parameter of trade-off threshold. Moreover, we present algorithm CB2S that splits the datasets into smaller pieces using the cluster algorithm of k-means and process queries in several small sets to retrieve more diverse results. The balance of similarity and diversity is decided through setting a threshold, which has a default value and can be adjusted according to users' preference. The performance and efficiency of our system are demonstrated through extensive experiments based on various da-tasets.
['Ruoxi Shi', 'Hongzhi Wang', 'Tao Wang', 'Yutai Hou', 'Yiwen Tang', 'Jianzhong Li', 'Hong Gao']
Similarity Search Combining Query Relaxation and Diversification