Optimizing top-k retrieval:submodularity analysis and search strategies

作     者：Chaofeng SHA Keqiang WANG Dell ZHANG Xiaoling WANG Aoying ZHOU 

作者机构：School of Computer ScienceShanghai Key Laboratory of Intelligent Information ProcessingFudan University Shanghai Key Laboratory of Trustworthy ComputingEast China Normal University Department of Computer Science and Information SystemsBirkbeckUniversity of London 

出 版 物：《Frontiers of Computer Science》 (计算机科学前沿(英文))

年 卷 期：2016年第10卷第3期

页      面：477-487页

核心收录：

学科分类：081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：was supported by the National Natural Science Foundation of China(Grant Nos.61572135 and 61170085) 973 project(2010CB328106) Program for New Century Excellent Talents in China(NCET-10-0388) 

主　　题：top-k retrieval diversification submodular function maximization 

摘      要：The key issue in top-fc retrieval,finding a set of fc documents(from a large document collection) that can best answer a user s query,is to strike the optimal balance between relevance and *** this paper,we study the top-fc retrieval problem in the framework of facility location analysis and prove the submodularity of that objective function which provides a theoretical approximation guarantee of factor 1--for the(best-first) greedy search ***,we propose a two-stage hybrid search strategy which first obtains a high-quality initial set of top-fc documents via greedy search,and then refines that result set iteratively via local *** on two large TREC benchmark datasets show that our two-stage hybrid search strategy approach can supersede the existing ones effectively and efficiently.