AF: Small: Efficient Algorithms for Querying Noisy Distributed/Streaming Datasets

本项目旨在研究分布式和流应用中噪声数据集的高效查询算法设计。噪声数据在当今世界是普遍存在的。在科学和商业数据库中，对相同的现实世界实体的不精确和不同的引用无处不在。这种噪音对准确的数据分析构成了重大障碍。作为“噪声数据”的一个例子，以YouTube视频为例。YouTube跟踪单个视频的观看量。然而，同一事件经常有许多类似的版本，使用当前的技术回答“有多少人观看了该事件？”这样的基本问题是具有挑战性的。该项目将提供新的技术和见解，以对抗大数据集的嘈杂性质，从而提高我们处理不断增长的商业和科学数据的能力。这个项目的成果将被整合到关于算法、数据库和数据挖掘的研究生和本科生课程三部曲中。PI将通过在会议/研讨会、大学、工业实验室以及网络媒体上发表演讲来传播研究成果。从技术上讲，这个项目试图回答以下问题：我们能否直接在有噪声的数据集上运行分布式和流算法，“在飞行中”解决噪声，并保持与无噪声设置相比的通信和空间效率？PI计划研究统计、关系和图形问题。这个项目有可能影响理论计算机科学中广泛的活跃研究领域，包括分布式和流算法、组测试、压缩感知、通信复杂性、聚类和局部敏感散列。

This project aims to study the design of efficient query algorithms for noisy datasets in distributed and streaming applications. Noisy data is universal in today's world. Imprecise and varying references to the same real-world entities are ubiquitous in scientific and commercial databases. This noise poses significant obstructions to accurate data analytics. As an example of "noisy data," consider YouTube videos. YouTube tracks the views of individual videos. However, there are frequently many similar versions of the same event and answering a basic question such as "How many people viewed this event?" is challenging using current techniques. This project will provide new techniques and insights to combat the noisy nature of large datasets, and hence will enhance our ability to process the ever-increasing quantity of business and scientific data. The products of this project will be integrated into a trilogy of graduate and undergraduate courses on algorithms, databases, and data mining. The PI will disseminate research outcomes by giving talks at conferences/workshops, universities, industrial labs, as well as online media.More technically, this project tries to answer the following question: can we run distributed and streaming algorithms directly on the noisy datasets, resolve the noise "on the fly", and retain communication and space efficiency compared with the noise-free setting? The PI plans to study statistical, relational and graph problems. This project has the potential to impact a wide range of active research areas in theoretical computer science, including distributed and streaming algorithms, group testing, compressed sensing, communication complexity, clustering, and locality sensitive hashing.