SHF: Small: Lazy Data Structures for Data-Intensive Applications

Suny At Binghamton, Binghamton NY

Investigators

Abstract

Developing and optimizing data-intensive applications is a crucial but challenging goal in the Big Data era. This project aims to research and design a novel programming system to improve the performance and assurance of data-intensive applications. The project's novelties are (i) laying a new foundation for programming, optimizing, and reasoning about Big Data systems, and (ii) building a practical software ecosystem to improve the quality of data-intensive applications. The project's impacts are (i) shedding fundamental insight in data-intensive programs, with a broad range of applications from social network analysis to artificial intelligence; (ii) enabling new curriculum development, and bringing underrepresented students to the exciting frontier of data-intensive computing. The project centers around the idea of data-centric laziness: the operations to be performed over data structures --- such as topological changes or payload queries --- may be delayed and flexibly memoized within the data structure itself in a decentralized manner. The project is carried out in several directions. First, it conducts a foundational study on laziness in the presence of data processing, including a rigorous study on the subtleties in designing a lazy propagation system, a proof of observable equivalence between lazy and eager data processing, a cost-based semantics for capturing lazy behaviors, and a unification of eagerness vs. laziness and data vs. computation. Second, it investigates how parallelism and laziness interact to improve the performance of lazy data structures, through the support of asynchronous data processing, in-data propagation parallelism, and concurrent garbage collection of propagation labels. Third, it bridges the language foundation with practical algorithm design and system building, exploring algorithm-oriented programming abstractions, partition-based out-of-core data processing, just-in-time data structure re-organization, and propagation-aware performance monitoring. 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.