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-Median问题，在输入来自欧几里得空间时扩展可分离数据的结果，改善滑动窗口模型中的界限，将核心技术技术与新型采样方法和平滑直方图的方法相结合。 PI的先前工作已经应用于自然语言处理，该项目将进一步扩展此方向，并探讨“第一层检测”的重要主题。此外，这项研究将探讨各种抽样和草图技术之间的相似性和差异，以及如何在大型多维天文数据库中使用它们，例如SDSS（Sloan Digital Sky Survey）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

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

Scalable streaming tools for analyzing N-body simulations: Finding halos and investigating excursion sets in one pass

• DOI: 10.1016/j.ascom.2018.04.003
• 发表时间: 2017-11
• 期刊: Astron. Comput.
• 作者: Nikita Ivkin;Zaoxing Liu;Lin F. Yang;Srinivas Suresh Kumar;G. Lemson;M. Neyrinck;A. Szalay;V. Braverman

Towards Fast and Scalable Graph Pattern Mining

迈向快速且可扩展的图形模式挖掘

• 发表时间: 2018
• 期刊: 10th {USENIX} Workshop on Hot Topics in Cloud Computing (HotCloud 18
• 作者: Iyer, A;Liu, Z;Jin, X;Venkataraman, S;Braverman, V;Stoica, I
• 通讯作者: Stoica, I