The New Jersey Institute of Technology's
Electronic Theses & Dissertations Project

Title:	Diversification and fairness in top-k ranking algorithms
Author:	Asadi, Mahsa
View Online:	njit-etd2023-035 (xii, 130 pages ~ 1.2 MB pdf)
Department:	Department of Computer Science
Degree:	Doctor of Philosophy
Program:	Computer Science
Document Type:	Dissertation
Advisory Committee:	Basu Roy, Senjuti (Committee chair) Wei, Zhi (Committee member) Koutis, Ioannis (Committee member) Theodoratos, Dimitri (Committee member) Amer-Yahia, Sihem (Committee member)
Date:	2023-08
Keywords:	Diversification Fairness Query processing Ranking Topk algorithms
Availability:	Unrestricted
Abstract:	Given a user query, the typical user interfaces, such as search engines and recommender systems, only allow a small number of results to be returned to the user. Hence, figuring out what would be the top-k results is an important task in information retrieval, as it helps to ensure that the most relevant results are presented to the user. There exists an extensive body of research that studies how to score the records and return top-k to the user. Moreover, there exists an extensive set of criteria that researchers identify to present the user with top-k results, and result diversification is one of them. Diversifying the top-k result ensures that the returned result set is relevant as well as representative of the entire set of answers to the user query, and it is highly relevant in the context of search, recommendation, and data exploration. The goal of this dissertation is two-fold: the first goal is to focus on adapting existing popular diversification algorithms and studying how to expedite them without losing the accuracy of the answers. This work studies the scalability challenges of expediting the running time of existing diversification algorithms by designing a generic framework that produces the same results as the original algorithms, yet it is significantly faster in running time. This proposed approach handles scenarios where data change over a period of time and studies how to adapt the framework to accommodate data changes. The second aspect of the work studies how the existing top-k algorithms could lead to inequitable exposure of records that are equivalent qualitatively. This scenario is highly important for long-tail data where there exists a long tail of records that have similar utility, but the existing top-k algorithm only shows one of the top-ks, and the rest are never returned to the user. Both of these problems are studied analytically, and their hardness is studied. The contributions of this dissertation lie in (a) formalizing principal problems and studying them analytically. (b) designing scalable algorithms with theoretical guarantees, and (c) evaluating the efficacy and scalability of the designed solutions by comparing them with the state-of-the-art solutions over large-scale datasets.