III: Small: Fairness-aware Data Structures for Approximate Query Processing

The abundance of data, coupled with recent advancements in computation, has revolutionized almost every aspect of modern life, and the central role of data structures in this revolution is undeniable. As data-driven technologies root in our lives, their drawbacks and potential harms when they make biased decisions become increasingly evident. To resolve such bias issues, this project revisits classical approximate query processing data structures through the lens of fairness. It envisions a future where fairness is a first-class citizen of database systems, where the potential fairness issues of database indices are identified and resolved. The project has the potential to involve under-represented minorities who find algorithmic fairness an interesting topic to which they can contribute. To effectively accomplish its objective, this project aims to design data structures with theoretical guarantees that achieve group fairness across domains such as hashing, membership estimation, aggregate query estimation, and approximate ranking and selection query answering. The ultimate objective is to develop a system for fair data structures for approximate query processing that can readily integrate into existing data management systems. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.