III: Small: Real-Time Detection of Structures from a Massive Graph Stream

III：小：从海量图流中实时检测结构

• 批准号: 1527541
• 负责人: Goce Trajcevski
• 金额: $ 49.99万
• 依托单位: Iowa State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1527541&HistoricalAwards=false
• 关键词: III; Small; Real; Time; Detection

There is an urgent need to quickly derive actionable intelligence from increasingly large volumes of data. In many domains, including social media analytics and cybersecurity, data contains relationships between entities that can be modeled using a graph, and a question on detecting patterns in data can be transformed into questions on detecting emerging structures in appropriately derived graphs. The goal of this project is to develop algorithms and software for finding significant structures from dynamic graphs in real-time. The project will develop algorithms that are efficient in their use of CPU and memory, and whose performance can be quantified in a mathematically rigorous way. The project will also develop implementations that are expected to process data at a highthroughput and can identify emerging structures much faster than current methods. The availability of these methods and implementations will impact the domains of cybersecurity and social network analytics. Software developed will be released as a toolkit of operators that can be used with current stream processing systems. The project will lead to new instructional material in existing courses as well as new courses in data analytics, involve individuals from underrepresented groups, and forge research collaborations with industrial research labs.The project will consider data that contains an evolving dynamic graph, and develop methods for detecting and enumerating change in the set of (1) dense combinatorial structures such as maximal cliques, quasi-cliques, maximal bicliques and quasi-bicliques in a graph, and (2) temporal structures such as temporal paths and temporal cliques in a time-stamped graph. While there has been significant progress in methods for detecting structures in a massive static graph, the same is not true for a dynamic graph, and often, the state-of-the-art for a dynamic graph is to repeatedly execute a method designed for a static graph. For enumerating the change in the set of structures, the project will take a novel approach of developing change-sensitive algorithms whose processing cost is proportional to the magnitude of change in the set of structures. It will use techniques from the area of approximation algorithms in designing (space and time) efficient methods for enumerating temporal structures from a graph stream. For further information, see the project web site at: http://www.ece.iastate.edu/~snt/nsf-iis2015/

迫切需要从日益庞大的数据中快速获取可操作的情报。在许多领域，包括社交媒体分析和网络安全，数据包含可以使用图建模的实体之间的关系，并且关于检测数据中的模式的问题可以转换为关于检测适当导出的图中的新兴结构的问题。该项目的目标是开发算法和软件，用于实时从动态图中找到重要结构。该项目将开发有效使用CPU和内存的算法，其性能可以以数学上严格的方式量化。该项目还将开发预期以高吞吐量处理数据的实现，并且可以比当前方法更快地识别新兴结构。这些方法和实现的可用性将影响网络安全和社交网络分析领域。开发的软件将作为操作员工具包发布，可用于当前的流处理系统。该项目将在现有课程中引入新的教学材料，并在数据分析方面引入新的课程，涉及来自代表性不足的群体的个人，并与工业研究实验室建立研究合作。该项目将考虑包含不断发展的动态图的数据，并开发用于检测和枚举（1）密集组合结构（如最大团，准团，图中的最大bicliques和准bicliques，以及（2）时间结构，例如时间戳图中的时间路径和时间团。 虽然在用于检测大规模静态图中的结构的方法中已经有了显著的进步，但是对于动态图来说，情况并非如此，并且通常，动态图的现有技术是重复执行为静态图设计的方法。为了枚举结构集的变化，该项目将采取一种新的方法，开发变化敏感的算法，其处理成本与结构集的变化幅度成正比。它将使用近似算法领域的技术来设计（空间和时间）有效的方法，用于从图形流中枚举时间结构。欲了解更多信息，请访问项目网站：http://www.ece.iastate.edu/~snt/nsf-iis2015/

项目成果

Incremental Maintenance of Maximal Bicliques in a Dynamic Bipartite Graph

• DOI: 10.1109/tmscs.2018.2802920
• 发表时间: 2018-07
• 期刊: IEEE Transactions on Multi-Scale Computing Systems
• 作者: A. Das;Srikanta Tirthapura

Weighted Reservoir Sampling from Distributed Streams

从分布式流中进行加权水库采样

• DOI: 10.1145/3294052.3319696
• 发表时间: 2019
• 期刊: Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
• 作者: Jayaram, Rajesh;Sharma, Gokarna;Tirthapura, Srikanta;Woodruff, David P.
• 通讯作者: Woodruff, David P.

Work-efficient parallel union-find: Work-efficient parallel union-find

高效工作的并行联合查找： 高效工作的并行联合查找

• DOI: 10.1002/cpe.4333
• 发表时间: 2018
• 期刊: Concurrency and Computation: Practice and Experience
• 作者: Simsiri, Natcha;Tangwongsan, Kanat;Tirthapura, Srikanta;Wu, Kun-Lung
• 通讯作者: Wu, Kun-Lung

Incremental maintenance of maximal cliques in a dynamic graph

• DOI: 10.1007/s00778-019-00540-5
• 发表时间: 2016-01
• 期刊: The VLDB Journal
• 作者: A. Das;Michael Svendsen;Srikanta Tirthapura

Stratified Random Sampling over Streaming and Stored Data

对流数据和存储数据进行分层随机采样

• DOI: 10.5441/002/edbt.2019.04
• 发表时间: 2019
• 期刊: Advances in Database Technology - 22nd International Conference on Extending Database Technology (EDBT
• 作者: Nguyen, T;Shih, M;Srivastava, D;Tirthapura, S
• 通讯作者: Tirthapura, S