AF: EAGER: Data Streaming with a View towards Cloud Computing

AF：EAGER：面向云计算的数据流

• 批准号: 1650992
• 负责人: Amit Chakrabarti
• 金额: $ 30万
• 依托单位: Dartmouth College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2019-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1650992&HistoricalAwards=false
• 关键词: AF; EAGER; Data; Streaming; View; AF; EAGER; Data; Streaming; View

The ability to efficiently and effectively process big data is becoming central to modern life. Increasingly, much of this processing takes place "in the cloud", on large clusters of powerful servers, which provide computational power far exceeding those available on a weak client, e.g., an end-user's personal computer. Many big data problems require time-and-space-efficient processing of massive data streams generated almost continuously: examples include financial transactions, medical records, and scientific experimentaldata. Access to a cloud computing service makes tractable a number of data streaming problems that would otherwise be intractable for a weak client.Existing cloud computing services do not give clients a guarantee that their computations will be executed error-free. In the course of this project, the PI will work to design and study the theoretical foundations of techniques that would enable a weak client to trust results arrived at when working withsuch a service. New algorithms designed during this project could have an impact on the practice of cloud computing and data streaming systems. The project will enable the training of graduate and undergraduate students in theoretical computer science research and exposition, and in experimentally studying algorithmic ideas relevant to such trustworthy cloud computing.The project has two major threads. The first is about algorithm design, wherein the PI will seek new or improved algorithms (in terms of space usage and communication costs) in the above weak-client/powerful-server setting. In particular, the PI will revisit such fundamental problems as norm estimation and clustering. The second thread is complexity-theoretic: the PI will seek to understand the limitations of this computational setting, most likely through proving new lower bounds in communication complexity. This thread naturally leads to open questions about Arthur-Merlin communication, a topic long known to be difficult enough that even small advances could be significant breakthroughs.

有效有效地处理大数据的能力正成为现代生活的核心。越来越多的处理过程“在云中”，在大量强大的服务器群上进行，提供的计算能力远远超过了弱客户端（例如最终用户的个人计算机）上可用的电源。许多大数据问题需要几乎连续生成的大量数据流的时间和空间处理：示例包括金融交易，医疗记录和科学实验数据。访问云计算服务使可处理的许多数据流问题否则对于弱客户端而言会很棘手。存在云计算服务不能保证客户的计算将无错误执行。在该项目的过程中，PI将致力于设计和研究技术的理论基础，这些技术将使弱客户能够信任与服务时的工作。在此项目中设计的新算法可能会影响云计算和数据流系统的实践。该项目将使理论计算机科学研究和博览会的研究生和本科生培训，并在实验研究与此类值得信赖的云计算相关的算法思想中。该项目具有两个主要主题。第一个是关于算法设计的，其中PI将在上述弱点/功能强大的服务器设置中寻求新的或改进的算法（就空间使用和通信成本而言）。特别是，PI将重新审视诸如规范估计和聚类等基本问题。第二个线程是复杂性理论：PI将寻求了解这种计算设置的局限性，这很可能是通过证明通信复杂性的新下限。该线程自然会导致有关Arthur-Merlin Communication的打开问题，这一主题已经足够困难，即使小进步也可能是重大突破。