CAREER:Foundation of Communication-Efficient Distributed Computation and Monitoring

职业：通信高效的分布式计算和监控的基础

• 批准号: 1844234
• 负责人: Qin Zhang
• 金额: $ 49.97万
• 依托单位: Indiana University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-06-01 至 2025-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1844234&HistoricalAwards=false
• 关键词: CAREER; Foundation; Communication; Efficient; Distributed

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.

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

项目成果

Communication complexity of approximate maximum matching in the message-passing model

消息传递模型中近似最大匹配的通信复杂度

• DOI: 10.1007/s00446-020-00371-6
• 发表时间: 2017-04
• 期刊: Distributed Computing
• 影响因子: 1.3
• 作者: Huang Zengfeng;Radunovic Bozidar;Vojnovic Milan;Zhang Qin
• 通讯作者: Zhang Qin

Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-armed Bandits

• DOI: 10.1109/focs.2019.00017
• 发表时间: 2019-04
• 期刊: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: Chao Tao;Qin Zhang;Yuanshuo Zhou

Distributed Partial Clustering

分布式部分集群

• DOI: 10.1145/3322808
• 发表时间: 2019
• 期刊: ACM Transactions on Parallel Computing
• 影响因子: 1.6
• 作者: Guha, Sudipto;Li, Yi;Zhang, Qin
• 通讯作者: Zhang, Qin

Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks

• DOI: 10.1007/s00453-018-00531-y
• 发表时间: 2011-08
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: Zengfeng Huang;K. Yi;Qin Zhang

SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins

• DOI: 10.14778/3565816.3565833
• 发表时间: 2022-10
• 期刊: Proc. VLDB Endow.
• 作者: Nikolai Karpov;Qin Zhang