research-article

Incremental diversification for very large sets: a streaming-based approach

Authors:

Wolfgang NejdlAuthors Info & Claims

SIGIR '11: Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval

Pages 585 - 594

https://doi.org/10.1145/2009916.2009996

Published: 24 July 2011 Publication History

Abstract

Result diversification is an effective method to reduce the risk that none of the returned results satisfies a user's query intention. It has been shown to decrease query abandonment substantially. On the other hand, computing an optimally diverse set is NP-hard for the usual objectives. Existing greedy diversification algorithms require random access to the input set, rendering them impractical in the context of large result sets or continuous data.

To solve this issue, we present a novel diversification approach which treats the input as a stream and processes each element in an incremental fashion, maintaining a near-optimal diverse set at any point in the stream. Our approach exhibits a linear computation and constant memory complexity with respect to input size, without significant loss of diversification quality. In an extensive evaluation on several real-world data sets, we show the applicability and efficiency of our algorithm for large result sets as well as for continuous query scenarios such as news stream subscriptions.

References

[1]

R. Agrawal, S. Gollapudi, A. Halverson, and S. Ieong. Diversifying search results. In WSDM, 2009.

Digital Library

[2]

S. Babu and J. Widom. Continuous queries over data streams. SIGMOD Record, 30(3):109--120, 2001.

Digital Library

[3]

D. F. Barbieri, D. Braga, S. Ceri, E. D. Valle, and M. Grossniklaus. C-sparql: Sparql for continuous querying. In WWW, 2009.

Digital Library

[4]

J. G. Carbonell and J. Goldstein. The use of MMR, diversity-based reranking for reordering documents and producing summaries. In SIGIR, 1998.

Digital Library

[5]

H. Chen and D. R. Karger. Less is more: probabilistic models for retrieving fewer relevant documents. In SIGIR, 2006.

Digital Library

[6]

J. Chen, D. J. DeWitt, F. Tian, and Y. Wang. NiagaraCQ: a scalable continuous query system for internet databases. In ACM SIGMOD, 2000.

Digital Library

[7]

C. L. Clarke, M. Kolla, G. V. Cormack, O. Vechtomova, A. Ashkan, S. Büttcher, and I. MacKinnon. Novelty and diversity in information retrieval evaluation. In SIGIR, 2008.

Digital Library

[8]

M. Drosou and E. Pitoura. Comparing diversity heuristics. Technical Report TR-2009-05, Comp. Sci. Department, University of Ioannina, Greece, 2009.

[9]

M. Drosou and E. Pitoura. Diversity over continuous data. IEEE Data Eng. Bull., 32(4):49--56, 2009.

[10]

M. Drosou, K. Stefanidis, and E. Pitoura. Preference-aware publish/subscribe delivery with diversity. In DEBS, 2009.

Digital Library

[11]

F. Giunchiglia. Managing Diversity in Knowledge. In IEA/AIE 2006, LNAI 4031, page 1, 2006.

[12]

S. Gollapudi and A. Sharma. An axiomatic approach for result diversification. In WWW, 2009.

Digital Library

[13]

J. R. Haritsa. The KNDN problem: A quest for unity in diversity. IEEE Data Eng. Bull., 32(4):15--22, 2009.

[14]

V. Hristidis, O. Valdivia, M. Vlachos, and P. S. Yu. A system for keyword search on textual streams. In SDM, 2007.

[15]

U. Irmak, S. Mihaylov, T. Suel, S. Ganguly, and R. Izmailov. Efficient query subscription processing for prospective search engines. In USENIX, 2006.

Digital Library

[16]

D. E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison Wesley, 1973.

[17]

D. G. McDonald and J. Dimmick. The conceptualization and measurement of diversity. Communication Research, 30(1):60--79, 2003.

[18]

E. Minack, G. Demartini, and W. Nejdl. Current approaches to search result diversification. In LivingWeb Workshop at ISWC, 2009.

[19]

G. Mishne and M. de Rijke. A study of blog search. In ECIR, 2006.

Digital Library

[20]

T.-W. Ryu, T. wan Ryu, and C. F. Eick. A unified similarity measure for attributes with set or bag of values. In RSDMGrC, 1998.

[21]

R. L. T. Santos, C. Macdonald, and I. Ounis. Exploiting query reformulations for web search result diversification. In WWW, 2010.

Digital Library

[22]

D. Skoutas, E. Minack, and W. Nejdl. Dealing with diversity in web search results. In WebSci10, 2010.

[23]

A. Slivkins, F. Radlinski, and S. Gollapudi. Learning optimally diverse rankings over large document collections. In ICML, 2010.

[24]

E. Vee, U. Srivastava, J. Shanmugasundaram, P. Bhat, and S. A. Yahia. Efficient computation of diverse query results. In ICDE, 2008.

Digital Library

[25]

J. Wang and J. Zhu. Portfolio theory of information retrieval. In SIGIR, 2009.

Digital Library

[26]

C. Yu, L. Lakshmanan, and S. Amer-Yahia. It takes variety to make a world: diversification in recommender systems. In EDBT, 2009.

Digital Library

[27]

C. Zhai, W. W. Cohen, and J. D. Lafferty. Beyond independent relevance: methods and evaluation metrics for subtopic retrieval. In SIGIR, 2003.

Digital Library

[28]

C. Zhai and J. D. Lafferty. A risk minimization framework for information retrieval. Inf. Process. Manage., 42(1):31--55, 2006.

Digital Library

[29]

C.-N. Ziegler, S. M. McNee, J. A. Konstan, and G. Lausen. Improving recommendation lists through topic diversification. In WWW, 2005.

Digital Library

Cited By

Wang KWang SCao XQin L(2022)Efficient Radius-Bounded Community Search in Geo-Social NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.304017234:9(4186-4200)Online publication date: 1-Sep-2022
https://doi.org/10.1109/TKDE.2020.3040172
Lyu BQin LLin XZhang YQian ZZhou J(2022)Maximum and top-k diversified biclique search at scaleThe VLDB Journal10.1007/s00778-021-00681-631:6(1365-1389)Online publication date: 18-Apr-2022
https://doi.org/10.1007/s00778-021-00681-6
Chen LShang SYang CLi J(2019)Spatial keyword search: a surveyGeoInformatica10.1007/s10707-019-00373-yOnline publication date: 4-Jul-2019
https://doi.org/10.1007/s10707-019-00373-y
Show More Cited By

Index Terms

Incremental diversification for very large sets: a streaming-based approach
1. Information systems
  1. Information retrieval

Recommendations

Exploring Diversification In Non-factoid Question Answering
ICTIR '18: Proceedings of the 2018 ACM SIGIR International Conference on Theory of Information Retrieval

Retrieving short, precise answers to non-factoid queries is an increasingly important task, especially for mobile and voice search. Many of these questions may have multiple or alternative answers. In an environment where answers are presented ...
Relationship between generalized rough sets based on binary relation and covering

Rough set theory is a powerful tool for dealing with uncertainty, granularity, and incompleteness of knowledge in information systems. This paper systematically studies a type of generalized rough sets based on covering and the relationship between this ...
The Willingness to Pay for Diversification
Diversification is a fundamental concept in economics and finance. This paper argues that decision makers have an intrinsic preference for diversification that is responsive to cost and that this willingness to pay for diversification is driven by risk ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGIR '11: Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval

July 2011

1374 pages

ISBN:9781450307574

DOI:10.1145/2009916

General Chairs:
Wei-Ying Ma
Microsoft Research Asia, China
,
Jian-Yun Nie
University of Montreal, Canada
,
Program Chairs:
Ricardo Baeza-Yates
Yahoo! Research, Spain
,
Tat-Seng Chua
National University of Singapore
,
W. Bruce Croft
University of Massachusetts, Amherst, USA

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGIR: ACM Special Interest Group on Information Retrieval

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 July 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGIR '11

Sponsor:

SIGIR

SIGIR '11: The 34th International ACM SIGIR conference on research and development in Information Retrieval

July 24 - 28, 2011

Beijing, China

Acceptance Rates

Overall Acceptance Rate 792 of 3,983 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

42
Total Citations
View Citations
692
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang KWang SCao XQin L(2022)Efficient Radius-Bounded Community Search in Geo-Social NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.304017234:9(4186-4200)Online publication date: 1-Sep-2022
https://doi.org/10.1109/TKDE.2020.3040172
Lyu BQin LLin XZhang YQian ZZhou J(2022)Maximum and top-k diversified biclique search at scaleThe VLDB Journal10.1007/s00778-021-00681-631:6(1365-1389)Online publication date: 18-Apr-2022
https://doi.org/10.1007/s00778-021-00681-6
Chen LShang SYang CLi J(2019)Spatial keyword search: a surveyGeoInformatica10.1007/s10707-019-00373-yOnline publication date: 4-Jul-2019
https://doi.org/10.1007/s10707-019-00373-y
Zhang FLin XZhang YQin LZhang W(2019)Efficient community discovery with user engagement and similarityThe VLDB Journal10.1007/s00778-019-00579-428:6(987-1012)Online publication date: 26-Oct-2019
https://doi.org/10.1007/s00778-019-00579-4
Wang YMeliou AMiklau G(2018)RC-indexProceedings of the VLDB Endowment10.14778/3192965.319296911:7(773-786)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.14778/3192965.3192969
Sacharidis DMehta PSkoutas DPatroumpas KVoisard ASacharidis DGamper JBöhlen M(2018)Selecting representative and diverse spatio-textual posts over sliding windowsProceedings of the 30th International Conference on Scientific and Statistical Database Management10.1145/3221269.3221290(1-12)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.1145/3221269.3221290
Song QWu YLin PDong LSun H(2018)Mining Summaries for Knowledge Graph SearchIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2018.280744230:10(1887-1900)Online publication date: 1-Oct-2018
https://doi.org/10.1109/TKDE.2018.2807442
Liu HJin CYang BZhou A(2018)Finding Top-k Shortest Paths with DiversityIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2017.277349230:3(488-502)Online publication date: 1-Mar-2018
https://doi.org/10.1109/TKDE.2017.2773492
Madhavi-Latha PMadhavi KGeetha G(2018)Advisory Search and Security on Data Mining using Clustering Approaches2018 Second International Conference on Inventive Communication and Computational Technologies (ICICCT)10.1109/ICICCT.2018.8473252(256-261)Online publication date: Apr-2018
https://doi.org/10.1109/ICICCT.2018.8473252
Sacharidis DMehta PSkoutas DPatroumpas KVoisard A(2017)Continuous Summarization of Streaming Spatio-Textual PostsProceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/3139958.3140027(1-4)Online publication date: 7-Nov-2017
https://dl.acm.org/doi/10.1145/3139958.3140027
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents