University of Minnesota
Top-k Subset Retrieval on Multidimensional Data: Diversity and Fairness
Abstract
dc:description.abstractSelecting 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.