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和内存的算法，并且可以以数学上严格的方式量化其性能。该项目还将开发预期将在高关注点处理数据的实现，并且可以比当前方法快得多地识别新兴结构。这些方法和实现的可用性将影响网络安全和社交网络分析的领域。开发的软件将作为运算符工具包发布，可与当前的流处理系统一起使用。 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图中的双晶和准双晶词，以及（2）时间stamp图中的时间路径和时间簇等时间结构。 尽管在大量静态图中检测结构的方法取得了重大进展，但对于动态图而言并非如此，而且通常，动态图的最新图像是重复执行为静态图设计的方法。为了列举结构集的变化，该项目将采用一种新的方法来开发对变更敏感的算法的处理算法，其处理成本与结构集的变化幅度成正比。它将在设计（时空和时间）有效方法中使用近似算法区域的技术来从图流列出时间结构。有关更多信息，请参见项目网站：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

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

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