Back to search

University of Minnesota

Top-k Subset Retrieval on Multidimensional Data: Diversity and Fairness

Abstract

dc:description.abstract

Selecting a subset of k "best" items in a dataset is important in information retrieval and decision-making. Recently, there has been growing concern that using automated algorithms for these tasks can result in decreased diversity and fairness, thereby promoting stereotypes and polarizing opinions. Several methods have been proposed to address this issue; however, most of the existing methods only work for a one-dimensional dataset, where a single attribute of each data point determines the top-k subset retrieval. In practice, multiple attributes are likely to be relevant, requiring top-k subset retrieval on multidimensional datasets. Only a few existing methods work on multidimensional data, and those that do are not efficient for large datasets. In this thesis, we consider two typical problems for diverse and fair top-k subset retrieval on multidimensional data, namely diverse top-k range search and fair top-k selection. We present our results for both the theoretical and practical aspects of these problems. On the theoretical side, we explore computational hardness landscapes that guide our algorithm design and present algorithms and data structures that are efficient and provide theoretical guarantees. On the practical side, we address engineering challenges and trade-offs to make the theoretically efficient solutions work in practice, and present solutions that, despite being theoretically suboptimal, demonstrate strong practical performance. Our experimental evaluation explores real-world scenarios, identifies areas critical to practical performance, and motivates computational hardness analysis in some cases. Through an end-to-end integrative methodology that bridges multiple (seemingly) disparate areas in theory and practice, we achieve substantial speedups and provide valuable insights into problem structure and algorithmic behavior.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Cai, Guangya

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Citation
Cai, Guangya. (2026). Top-k Subset Retrieval on Multidimensional Data: Diversity and Fairness. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/282286.

Chain of custody

source
Harvested from
University of Minnesota
Base URL
conservancy.umn.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Cai, Guangya. Top-k Subset Retrieval on Multidimensional Data: Diversity and Fairness. 2026. https://hdl.handle.net/11299/282286