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计划研究统计，关系和图形问题。 该项目有可能影响理论计算机科学的广泛活跃研究领域，包括分布式和流媒体算法，组测试，压缩感应，沟通复杂性，聚类和局部敏感性散列。

项目成果

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

EmbedJoin: Efficient Edit Similarity Joins via Embeddings

• DOI: 10.1145/3097983.3098003
• 发表时间: 2017-01-01
• 期刊: KDD'17: PROCEEDINGS OF THE 23RD ACM SIGKDD INTERNATIONAL CONFERENCE ON KNOWLEDGE DISCOVERY AND DATA MINING
• 作者: Zhang, Haoyu;Zhang, Qin
• 通讯作者: Zhang, Qin

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