BIGDATA: F: DKA: Collaborative Research: Clustering Algorithms for Data Streams

BIGDATA：F：DKA：协作研究：数据流的聚类算法

• 批准号: 1447639
• 负责人: Vladimir Braverman
• 金额: $ 100万
• 依托单位: Johns Hopkins University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1447639&HistoricalAwards=false
• 关键词: BIGDATA; DKA; Collaborative; Research; Clustering

This project will develop novel theoretical methods and algorithms for clustering massive datasets with applications to astronomy, neuroscience and natural language processing. Clustering is the process of creating groups of data based on similarities between individual data points. The developed theoretical methods will be used in applications where clustering algorithms are critical and the input data is extremely large. First, new clustering algorithms will be designed to scale and will allow for better cosmological simulations. The simulations involve billions of particles in each snapshot, and existing clustering algorithms based upon a simple friends-of-friends approach do not scale to these cardinalities. Second, this project will advance the computational capabilities in statistical neuroscience by employing clustering algorithms to discover both regular patterns and anomalies in normal and abnormal brain graphs. Finally, this research will explore the important topic of finding anomalies in massive text streams, such as Twitter. In this setting, one is concerned with detecting anomalous bursts in traffic content that share a similar pattern. These bursts might signal an important political event or a natural disaster. This project will support undergraduate and graduate research aimed at developing skills needed for algorithmic work on massive data sets.There exist numerous heuristics and approximation algorithms for many variants of the clustering problem. However, these methods are often slow or infeasible for applications with massive datasets. This research will improve space and time upper bounds for clustering algorithms in the streaming model. This project will address the k-mean and k-median problems in the dynamic streaming model, extend the results on separable data when the input comes from Euclidian space, improve the bounds in the sliding window model, combine the coresets technique with novel sampling approaches and the method of smooth histograms. The PIs' previous work has already been applied to natural language processing and this project will expand this direction further and explore the important topic of "First Story Detection." Furthermore, this research will explore the similarities and differences between various sampling and sketching techniques, and how they could be used in large multidimensional astronomical databases, like SDSS (Sloan Digital Sky Survey) SkyServer. These novel approaches will provide major speedups for the execution of large statistical aggregate queries. The new streaming algorithms will be used to find substructure in very large cosmological N-body simulations. For further information see the project web site at: http://www.cs.jhu.edu/~vova

该项目将开发新的理论方法和算法，用于天文学、神经科学和自然语言处理领域的海量数据集聚类。聚类是基于单个数据点之间的相似性创建数据组的过程。所开发的理论方法将用于聚类算法至关重要和输入数据非常大的应用中。首先，新的聚类算法将被设计成可扩展的，并将允许更好的宇宙模拟。模拟涉及每个快照中的数十亿个粒子，现有的基于简单的朋友-朋友方法的聚类算法无法扩展到这些基数。其次，该项目将通过使用聚类算法来发现正常和异常脑图中的规则模式和异常，从而提高统计神经科学的计算能力。最后，本研究将探讨在大量文本流（如Twitter）中发现异常的重要主题。在此设置中，我们关注的是检测具有相似模式的流量内容中的异常突发。这些爆发可能预示着一个重要的政治事件或自然灾害。该项目将支持本科生和研究生的研究，旨在开发大规模数据集算法工作所需的技能。对于聚类问题的许多变体，存在许多启发式和近似算法。然而，这些方法对于具有大量数据集的应用程序通常很慢或不可行。本研究将改进流模型中聚类算法的空间和时间上界。本项目将解决动态流模型中的k-均值和k-中值问题，扩展输入来自欧几里德空间的可分离数据的结果，改进滑动窗口模型中的边界，将核心集技术与新颖的采样方法和平滑直方图方法相结合。pi先前的工作已经应用于自然语言处理，该项目将进一步扩展这一方向，探索“第一故事检测”这一重要课题。此外，本研究将探索各种采样和素描技术之间的异同，以及它们如何在大型多维天文数据库中使用，如SDSS（斯隆数字巡天）SkyServer。这些新颖的方法将大大加快大型统计聚合查询的执行速度。新的流算法将用于在非常大的宇宙n体模拟中寻找子结构。欲了解更多信息，请参阅该项目的网站：http://www.cs.jhu.edu/~vova

项目成果

Streaming symmetric norms via measure concentration

• DOI: 10.1145/3055399.3055424
• 发表时间: 2015-11
• 期刊: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Jarosław Błasiok;Vladimir Braverman;Stephen R. Chestnut;Robert Krauthgamer;Lin F. Yang

Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows

• DOI: 10.4230/lipics.approx-random.2018.7
• 发表时间: 2018-05
• 期刊: ArXiv
• 作者: V. Braverman;Elena Grigorescu;Harry Lang;David P. Woodruff;Samson Zhou

Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order

• 发表时间: 2016-09
• 作者: V. Braverman;Stephen R. Chestnut;Robert Krauthgamer;Yi Li;David P. Woodruff;Lin F. Yang

Approximate Convex Hull of Data Streams

• DOI: 10.4230/lipics.icalp.2018.21
• 发表时间: 2017-12
• 期刊: ArXiv
• 作者: Avrim Blum;V. Braverman;Ananya Kumar;Harry Lang;Lin F. Yang

Revisiting Frequency Moment Estimation in Random Order Streams

重新审视随机顺序流中的频率矩估计

• 发表时间: 2018
• 期刊: and Programming (ICALP 2018
• 作者: Braverman, Vladimir;Woodruff, David;Yang, Lin
• 通讯作者: Yang, Lin