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

在大数据时代，开发和优化数据密集型应用程序是一个至关重要但具有挑战性的目标。本项目旨在研究和设计一种新的编程系统，以提高数据密集型应用程序的性能和保证。该项目的新颖之处在于(i)为大数据系统的编程、优化和推理奠定了新的基础，（ii）构建了一个实用的软件生态系统，以提高数据密集型应用程序的质量。该项目的影响是：(1)揭示了数据密集型项目的基本见解，具有从社交网络分析到人工智能的广泛应用；（ii）推动新课程的发展，并将未被充分代表的学生带到令人兴奋的数据密集型计算前沿。该项目围绕着以数据为中心的惰性思想：对数据结构执行的操作——比如拓扑更改或有效负载查询——可能会被延迟，并以分散的方式灵活地存储在数据结构本身中。该项目在几个方向上进行。首先，它对数据处理中的惰性进行了基础研究，包括对设计惰性传播系统的微妙之处进行了严格的研究，证明了惰性和渴望数据处理之间的可观察等价性，用于捕获懒惰行为的基于成本的语义，以及渴望与懒惰和数据与计算的统一。其次，通过支持异步数据处理、数据内传播并行性和传播标签的并发垃圾收集，研究并行性和惰性如何相互作用以提高惰性数据结构的性能。第三，它将语言基础与实际算法设计和系统构建联系起来，探索面向算法的编程抽象、基于分区的核外数据处理、实时数据结构重组和传播感知性能监控。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.