CAREER:Foundation of Communication-Efficient Distributed Computation and Monitoring

通过移动设备的大量使用、数据云以及物联网的兴起，大量数据被生成、数字化和分析，以造福社会。由于数据通常是在不同的地点收集和维护的，因此通信对于几乎所有的计算任务都是必要的。此外，决策者自然希望及时维护所有数据的集中视图，这需要对分布式数据进行频繁查询，在极端情况下，还需要持续监控查询输出。通信成本自然成为这类应用的瓶颈。该项目旨在为分布式计算和监控开发通信高效的解决方案。这些产品将被整合到数据科学基础课程的三部曲中。该项目将涉及培训各级学生，重点是性别多样性和代表性不足群体的参与。本项目针对分布式计算的三个基本方面：(1)分布式一次计算中通信成本与计算轮数之间的权衡，(2)数据分区的能力，(3)分布式一次计算与连续监控之间的联系。PI将通过研究数据库、数据挖掘、网络和机器学习中的基本算法问题来接近这些方向。通信高效计算和监控的系统理论有可能影响大数据理论基础的广泛快速发展领域，包括流算法、草图算法、并行和分布式计算。它还将加深我们对理论计算机科学和数学中的通信复杂性和信息理论的理解。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Through the massive use of mobile devices, data clouds, and the rise of the Internet of Things, large amounts of data have been generated, digitized, and analyzed for the benefit of society. As data are often collected and maintained at different sites, communication has become necessary for nearly every computational task. Moreover, decision makers naturally want to maintain a centralized view of all the data in a timely manner, which requires frequent queries on the distributed data and, in the extreme, continuous monitoring of the query output. The cost of communication has naturally become the bottleneck for such applications. This project aims to develop communication-efficient solutions for distributed computation and monitoring. The products will be integrated into a trilogy of courses in the foundations of data science. The project will involve training students at all levels, with an emphasis on gender diversity and participation of underrepresented groups. This project targets three fundamental aspects of distributed computation: (1) the tradeoffs between the communication cost and the number of rounds of the computation in distributed one-shot computation, (2) the power of data partitioning, and (3) the connections between distributed one-shot computation and continuous monitoring. The PI will approach these directions via the study of fundamental algorithmic problems in databases, data mining, networking, and machine learning. A systematic theory of communication-efficient computation and monitoring has the potential to impact a wide range of rapidly developing areas in theoretical foundations of big data, including streaming algorithms, sketching algorithms, and parallel and distributed computing. It will also deepen our understanding of communication complexity and information theory in theoretical computer science and mathematics.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.