Computer Science ›› 2017, Vol. 44 ›› Issue (8): 181-186.doi: 10.11896/j.issn.1002-137X.2017.08.032

Previous Articles     Next Articles

Diverse Ranking Algorithm Based on Minimal Independent Dominating Set

YIN Jia, CHENG Chun-ling and ZHOU Jian   

  • Online:2018-11-13 Published:2018-11-13

Abstract: 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.

Key words: Diverse ranking,Query processing,Minimal independent dominating set,Abandoned subset

[1] SANTOS R L T,PENG J,MACDONALD C,et al.ExplicitSearch Result Diversification through Sub-queries[C]∥Proceedings of the 32nd European Conference on Advances in Information Retrieval.ACM,2010:87-99.
[2] OZDEMIRAY A M,ALTINGOVDE I S.Explicit search result diversification using score and rank aggregation methods[J].Journal of the Association for Information Science & Technology,2015,66(2):1212-1228.
[3] REN P J,CHEN Z M,MA J,et al.Search result diversification combing semantic and temporal intent[J].Chinese Journal of Computers,2015,8(10):2076-2091.(in Chinese) 任鹏杰,陈竹敏,马军,等.一种综合语义和时效性意图的检索结果多样化方法[J].计算机学报,2015,38(10):2076-2091.
[4] WU S L,HUANG C L.Search result diversification via data fusion[C]∥Proceedings of the 37th International ACM SIGIR Conference on Research & Development in Information Retrie-val.ACM,2014:827-830.
[5] YU H T,REN F.Search Result Diversification via Filling Up Multiple Knapsacks[C]∥Proceedings of the 23rd ACM International Conference on Information and Knowledge Management.ACM,2014:609-618.
[6] HU S,DOU Z,WANG X,et al.Search Result Diversification Based on Hierarchical Intents[C]∥Proceedings of the 24th ACM International on Conference on Information and Know-ledge Management.ACM,2015:63-72.
[7] RADLINSKI F,KLEINBERG R,JOACHIMS T.Learning diverse rankings with multi-armed bandits[C]∥Proceedings of the 25th International Conference on Machine Learning.ACM,2008:784-791.
[8] SCHUTH A,OOSTERHUIUS H,WHITESON S,et al.Multileave Gradient Descent for Fast Online Learning to Rank[C]∥Proceedings of the Ninth ACM International Conference on Web Search and Data Mining.ACM,2016:457-466.
[9] OOSTERHUIUS H,SCHUTH A,DE RIJKE M.Probabilistic Multileave Gradient Descent[C]∥Proceedings of the 38th European Conference on IR Research.2016:661-668.
[10] CARBONELL J,GOLDSTEIN J.The use of MMR,diversity-based re-ranking for reordering documents and producing summaries[C]∥Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.ACM,1998:335-336.
[11] XIA L,XU J,LAN Y,et al.Learning Maximal Marginal Relevance Model via Directly Optimizing Diversity Evaluation Mea-sures[C]∥Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval.2015:113-122.
[12] ZHU X J,GOLDBERG,et al.Improving Diversity in Rankingusing Absorbing Random Walks[C]∥Proceedings of the North American Chapter of the Association for Computational Linguistics Conference on Human Language Technology.2007:97-104.
[13] ZHU Y,LAN Y,GUO J,et al.Learning for search result diversification[C]∥Proceedings of the 37th International ACM SIGIR Conference on Research & Development in Information Retrieval.ACM,2014:293-302.
[14] CARPINETO.AMBIENT Dataset[EB/OL].http://credo.fub.it/ambient.
[15] ZHAI C X,COHEN W W,LAFFERTY J.Beyond independent relevance:methods and evaluation metrics for subtopic retrieval[C]∥Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.ACM,2003:10-17.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!