XTRIPODS: Algorithms and Machine Learning in Data Intensive Models

San Diego State University Foundation, San Diego CA

Investigators

Abstract

Large datasets have emerged within numerous scientific disciplines, unveiling valuable insights and helping to develop various useful applications. However, they also pose several challenges due to their ever-growing size and dynamic nature. Often, these data sets are processed as data streams or distributed across multiple machines. Sketching and streaming algorithms have been successful in tackling many problems in these settings, ranging from data analysis, network algorithms, to optimization. One research objective of this project is to further improve these algorithms, in terms of time and memory efficiency, with the aid of machine learning predictions. This project will also apply sketching techniques to develop federated machine learning algorithms where data is distributed across machines or devices, offering privacy advantages due to their decentralized nature. The project also aims to improve the foundation of data science and computer science education at San Diego State University and in the community at large through collaboration with the TRIPODS EnCore Institute at UC San Diego. Unlike traditional worst-case analysis, by incorporating machine learning to unravel the underlying structure of the data, it becomes possible in many cases to design better algorithms. The investigator plans to improve the efficiency of existing sketching and streaming algorithms using machine learning. These improvements are in terms of space and time complexity as well as approximation quality. A wide range of problems in this paradigm including data summarization, graph theory, and combinatorial optimization will be considered. Additionally, the investigator plans to utilize sketching to aid the design of machine learning algorithms in distributed and federated settings. Data sketches offer several advantages for this task. They have a small memory footprint and can be merged to form a sketch of the combined data. Additionally, they reveal minimal information about local data, benefiting privacy. The investigator aims to employ sketching algorithms on various problems such as building boosted decision trees for classification and regression, and learning a Bayesian network to explain the data. The investigator will also develop new computer science courses at San Diego State University to improve data science education and collaborate with the TRIPODS EnCORE Institute at UC San Diego, to expand a summer boot camp for high school students focusing on data science. 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.