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

AF：小：查询嘈杂分布式/流数据集的高效算法

• 批准号: 1525024
• 负责人: Qin Zhang
• 金额: $ 44.43万
• 依托单位: Indiana University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-06-15 至 2019-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1525024&HistoricalAwards=false
• 关键词: AF; Small; Efficient; Algorithms; Querying

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.

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

项目成果

Distributed Statistical Estimation of Matrix Products with Applications

• DOI: 10.1145/3196959.3196964
• 发表时间: 2018-05
• 期刊: Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
• 作者: David P. Woodruff;Qin Zhang

Communication-Efficient Distributed Skyline Computation

• DOI: 10.1145/3132847.3132927
• 发表时间: 2017-11
• 期刊: Proceedings of the 2017 ACM on Conference on Information and Knowledge Management
• 作者: Haoyu Zhang;Qin Zhang

A Practical Algorithm for Distributed Clustering and Outlier Detection

• 发表时间: 2018-05
• 作者: Jiecao Chen;Erfan Sadeqi Azer;Qin Zhang

MinJoin: Efficient Edit Similarity Joins via Local Hash Minima

• DOI: 10.1145/3292500.3330853
• 发表时间: 2018-10
• 期刊: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining
• 作者: Haoyu Zhang;Qin Zhang

Bias-Aware Sketches

• DOI: 10.14778/3099622.3099627
• 发表时间: 2016-10
• 期刊: Proc. VLDB Endow.
• 作者: Jiecao Chen;Qin Zhang