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-mean和k-median问题，扩展可分离数据的结果，当输入来自欧氏空间时，改进滑动窗口模型中的边界，将coresets技术与新的采样方法和平滑直方图方法相结合。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