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

项目成果

期刊论文数量（8）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Communication-Efficient Distributed Skyline Computation

通信高效的分布式 Skyline 计算

DOI：
10.1145/3132847.3132927
发表时间：
2017-11-06
期刊：
Proceedings of the 2017 ACM on Conference on Information and Knowledge Management
影响因子：
0
作者：
Haoyu Zhang;Qin Zhang
通讯作者：
Qin Zhang

Smooth q-Gram, and Its Applications to Detection of Overlaps among Long, Error-Prone Sequencing Reads

平滑 q-Gram 及其在长、易错测序读取之间重叠检测中的应用

DOI：
10.1145/3269206.3271688
发表时间：
2018-01
期刊：
ACM International Conference on Information and Knowledge Management
影响因子：
0
作者：
Zhang, H;Zhang, Q;Tang, H
通讯作者：
Tang, H

A Practical Algorithm for Distributed Clustering and Outlier Detection

分布式聚类和异常值检测的实用算法

DOI：
发表时间：
2018-05-24
期刊：
影响因子：
0
作者：
Jiecao Chen;Erfan Sadeqi Azer;Qin Zhang
通讯作者：
Qin Zhang

EmbedJoin: Efficient Edit Similarity Joins via Embeddings

EmbedJoin：通过嵌入进行高效编辑相似性连接

DOI：
10.1145/3097983.3098003
发表时间：
2017-02-01
期刊：
Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
影响因子：
0
作者：
Haoyu Zhang;Qin Zhang
通讯作者：
Qin Zhang

Distributed Statistical Estimation of Matrix Products with Applications

矩阵乘积的分布式统计估计及其应用

DOI：
10.1145/3196959.3196964
发表时间：
2018-05-27
期刊：
Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
影响因子：
0
作者：
David P. Woodruff;Qin Zhang
通讯作者：
Qin Zhang