Online set selection with fairness and diversity constraints

Julia Stoyanovich, Ke Yang, H. V. Jagadish

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    Selection algorithms usually score individual items in isolation, and then select the top scoring items. However, often there is an additional diversity objective. Since diversity is a group property, it does not easily jibe with individual item scoring. In this paper, we study set selection queries subject to diversity and group fairness constraints. We develop algorithms for several problem settings with streaming data, where an online decision must be made on each item as it is presented. We show through experiments with real and synthetic data that fairness and diversity can be achieved, usually with modest costs in terms of quality. Our experimental evaluation leads to several important insights in online set selection. We demonstrate that theoretical guarantees on solution quality are conservative in real datasets, and that tuning the length of the score estimation phase leads to an interesting accuracy-efficiency trade-off. Further, we show that if a difference in scores is expected between groups, then these groups must be treated separately during processing. Otherwise, a solution may be derived that meets diversity constraints, but that selects lower-scoring members of disadvantaged groups.

    Original languageEnglish (US)
    Title of host publicationAdvances in Database Technology - EDBT 2018
    Subtitle of host publication21st International Conference on Extending Database Technology, Proceedings
    EditorsMichael Bohlen, Reinhard Pichler, Norman May, Erhard Rahm, Shan-Hung Wu, Katja Hose
    Number of pages12
    ISBN (Electronic)9783893180783
    StatePublished - 2018
    Event21st International Conference on Extending Database Technology, EDBT 2018 - Vienna, Austria
    Duration: Mar 26 2018Mar 29 2018

    Publication series

    NameAdvances in Database Technology - EDBT
    ISSN (Electronic)2367-2005


    Conference21st International Conference on Extending Database Technology, EDBT 2018

    ASJC Scopus subject areas

    • Information Systems
    • Software
    • Computer Science Applications


    Dive into the research topics of 'Online set selection with fairness and diversity constraints'. Together they form a unique fingerprint.

    Cite this