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 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

SyncSignature: a simple, efficient, parallelizable framework for tree similarity joins

SyncSignature：一个简单、高效、可并行的树相似性连接框架

• DOI: 10.14778/3565816.3565833
• 发表时间: 2023-08
• 期刊: Proceedings of the VLDB Endowment
• 影响因子: 2.5
• 作者: Karpov, Nikolai;Zhang, Qin
• 通讯作者: Zhang, Qin

MinJoin: Efficient Edit Similarity Joins via Local Hash Minima

MinJoin：通过本地哈希最小值进行高效编辑相似性连接

• 发表时间: 2019-08
• 期刊: ACM SIGKDD Conference on Knowledge Discovery and Data Mining
• 作者: Zhang, H;Zhang, Q
• 通讯作者: Zhang, Q

Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks

用于跟踪分布式计数、频率和排名的随机算法

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

Communication-Efficient Collaborative Regret Minimization in Multi-Armed Bandits

多臂强盗中有效沟通的协作遗憾最小化

• 发表时间: 2024-02
• 期刊: Proceedings of the AAAI Conference on Artificial Intelligence
• 作者: Karpov, Nikolai;Zhang, Qin
• 通讯作者: Zhang, Qin

Communication-Efficient Collaborative Best Arm Identification

高效沟通的协作最佳手臂识别

• 发表时间: 2023-02
• 期刊: Proceedings of the AAAI Conference on Artificial Intelligence
• 作者: Karpov, Nikolai;Zhang, Qin
• 通讯作者: Zhang, Qin