skip to main content
10.1145/2348283.2348296acmconferencesArticle/Chapter ViewAbstractPublication PagesirConference Proceedingsconference-collections
research-article

Diversity by proportionality: an election-based approach to search result diversification

Published: 12 August 2012 Publication History

Abstract

This paper presents a different perspective on diversity in search results: diversity by proportionality. We consider a result list most diverse, with respect to some set of topics related to the query, when the number of documents it provides on each topic is proportional to the topic's popularity. Consequently, we propose a framework for optimizing proportionality for search result diversification, which is motivated by the problem of assigning seats to members of competing political parties. Our technique iteratively determines, for each position in the result ranked list, the topic that best maintains the overall proportionality. It then selects the best document on this topic for this position. We demonstrate empirically that our method significantly outperforms the top performing approach in the literature not only on our proposed metric for proportionality, but also on several standard diversity measures. This result indicates that promoting proportionality naturally leads to minimal redundancy, which is a goal of the current diversity approaches.

References

[1]
R. Agrawal, S. Gollapudi, A. Halverson, and S. Ieong. Diversifying search results. In Proceedings of WSDM, pages 5--14, 2009.
[2]
R. Baeza-Yates, C. Hurtado and M. Mendoza. Query recommendation using query logs in search engines. In The ClustWeb Workshop, pages 588--596, 2004.
[3]
M. Bendersky, D. Fisher, and W.B. Croft. UMass at TREC 2010 Web Track: Term dependence, spam filtering and quality bias. In Proceedings of TREC, 2010.
[4]
J. Carbonell and J. Goldstein. The use of MMR, diversity-based reranking for reordering documents and producing summaries. In Proceedings SIGIR, pages 335--336, 1998.
[5]
B. Carterette and P. Chandar. Probabilistic models of ranking novel documents for faceted topic retrieval. In Proceedings of CIKM, pages 1287--1296, 2009.
[6]
O. Chapelle, D. Metlzer, Y. Zhang, and P. Grinspan. Expected reciprocal rank for graded relevance. In Proceedings of CIKM, pages 621--630, 2009.
[7]
C.L.A. Clarke, M. Kolla, G.V. Cormack, O. Vechtomova, A. Ashkan, S. Buttcher, and I. MacKinnon. Novelty and diversity in information retrieval evaluation. In Proceedings of SIGIR, pages 659--666, 2008.
[8]
C.L.A. Clarke, M. Kolla, and O. Vechtomova. An effectiveness measure for ambiguous and underspecified queries. In Proceedings of ICTIR, pages 188--199, 2009.
[9]
C.L.A. Clarke, N. Craswell, I. Soboroff, and A. Ashkan. A comparative analysis of cascade measures for novelty and diversity. In Proceedings of WSDM, pages 75--84, 2011.
[10]
C.L.A. Clarke, N. Craswell, and I. Soboroff. Overview of the TREC 2009 Web track. In TREC, 2009.
[11]
C.L.A. Clarke, N. Craswell, I. Soboroff, and G.V. Cormack. Overview of the TREC 2009 Web track. In TREC, 2009.
[12]
G.V. Cormack, M.D. Smucker, and C.L.A. Clarke. Efficient and effective spam filtering and re-ranking for large web datasets. Apr 2010.
[13]
N. Craswell, O. Zoeter, M.J. Taylor, and B. Ramsey. An experimental comparison of click position-bias models. In Proceedings of WSDM, pages 87--94, 2008.
[14]
W.B. Croft, D. Metzler, and T. Strohman. Search Engines: Information Retrieval in Practice. Addison-Wesley, 2009.
[15]
V. Dang and W.B. Croft. Query reformulation using anchor text. In Proceedings of WSDM, pages 41--50, 2010.
[16]
V. Dang, X. Xue, and W.B. Croft. Inferring query aspects from reformulations using clustering. In Proceedings of CIKM, pages 2117--2120, 2011.
[17]
M. Gallagher. Proportionality, disproportionality and electoral systems. In Electoral Studies, 10(1):33--51, 1991.
[18]
R. Jones, B. Rey and O. Madani. Generating query substitutions. In Proceedings of WWW, pages 387--396, 2006.
[19]
A. Lijphart. Electoral systems and party systems: A study of twenty-seven democracies, 1945--1990. Oxford University Press, 1994.
[20]
Q. Mei, D. Zhou and K. Church. Query suggestion using hitting time. In Proceedings of CIKM, pages 469--477, 2008.
[21]
D. Metzler and W.B. Croft. Latent concept expansion using markov random fields. In Proceedings of SIGIR, pages 311--318, 2007.
[22]
D. Rafiei, K. Bharat and A. Shukia. Diversifying web search results. In Proceedings of WWW, page 781--790, 2010.
[23]
F. Radlinski and S. Dumais. Improving personalized web search using result diversification. In Proceedings of SIGIR, pages 691--692, 2006.
[24]
X. Wang and C. Zhai. Mining term association patterns from search logs for effective query reformulation. In Proceedings of CIKM, pages 479--488, 2008.
[25]
J. Wang and J. Zhu. Portfolio theory of information retrieval. In Proceedings of SIGIR, pages 115--122, 2009.
[26]
R. L. T. Santos, C. Macdonald, and I. Ounis. Exploiting query reformulations for web search result diversification. In Proceedings of WWW, pages 881--890, 2010.
[27]
R. L. T. Santos, C. Macdonald, and I. Ounis. Selectively diversifying web search results. In Proceedings of CIKM, pages 1179--1188, 2010.
[28]
R. L. T. Santos, C. Macdonald, and I. Ounis. Intent-aware search result diversification. In Proceedings of SIGIR, pages 595--604, 2011.
[29]
C. Zhai, W.W. Cohen, and J. Lafferty. Beyond independent relevance: Methods and evaluation metrics for subtopic retrieval. In Proceedings of SIGIR, pages 10--17, 2003.

Cited By

View all
  • (2025)Fairness and Diversity in Recommender Systems: A SurveyACM Transactions on Intelligent Systems and Technology10.1145/366492816:1(1-28)Online publication date: 3-Jan-2025
  • (2024)Passage-aware Search Result DiversificationACM Transactions on Information Systems10.1145/365367242:5(1-29)Online publication date: 13-May-2024
  • (2024)Multi-grained Document Modeling for Search Result DiversificationACM Transactions on Information Systems10.1145/365285242:5(1-22)Online publication date: 27-Apr-2024
  • Show More Cited By

Index Terms

  1. Diversity by proportionality: an election-based approach to search result diversification

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    SIGIR '12: Proceedings of the 35th international ACM SIGIR conference on Research and development in information retrieval
    August 2012
    1236 pages
    ISBN:9781450314725
    DOI:10.1145/2348283
    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

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 12 August 2012

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. novelty
    2. proportional representation
    3. proportionality
    4. redundancy
    5. sainte-lague
    6. search result diversification

    Qualifiers

    • Research-article

    Conference

    SIGIR '12
    Sponsor:

    Acceptance Rates

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

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)56
    • Downloads (Last 6 weeks)5
    Reflects downloads up to 20 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2025)Fairness and Diversity in Recommender Systems: A SurveyACM Transactions on Intelligent Systems and Technology10.1145/366492816:1(1-28)Online publication date: 3-Jan-2025
    • (2024)Passage-aware Search Result DiversificationACM Transactions on Information Systems10.1145/365367242:5(1-29)Online publication date: 13-May-2024
    • (2024)Multi-grained Document Modeling for Search Result DiversificationACM Transactions on Information Systems10.1145/365285242:5(1-22)Online publication date: 27-Apr-2024
    • (2024)Ranking with Slot ConstraintsProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3672000(956-967)Online publication date: 25-Aug-2024
    • (2024)Rethinking 'Complement' Recommendations at Scale with SIMDProceedings of the 15th ACM/SPEC International Conference on Performance Engineering10.1145/3629526.3645041(25-36)Online publication date: 7-May-2024
    • (2024)An Evaluation Framework for Attributed Information Retrieval using Large Language ModelsProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679172(5354-5359)Online publication date: 21-Oct-2024
    • (2024)Fairness-Aware Exposure Allocation via Adaptive RerankingProceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3626772.3657794(1504-1513)Online publication date: 10-Jul-2024
    • (2024)CL4DIV: A Contrastive Learning Framework for Search Result DiversificationProceedings of the 17th ACM International Conference on Web Search and Data Mining10.1145/3616855.3635851(171-180)Online publication date: 4-Mar-2024
    • (2024)Integrated Personalized and Diversified Search Based on Search LogsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.329100636:2(694-707)Online publication date: 1-Feb-2024
    • (2024)Sampling-based epoch differentiation calibrated graph convolution network for point-of-interest recommendationNeurocomputing10.1016/j.neucom.2023.127140571(127140)Online publication date: Feb-2024
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media