• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
Iowa State University
College of Engineering

Srikanta Tirthapura

  • Home
  • Research Group
  • Publications
  • Teaching
  • Professional Service
  • News

National Science Foundation Project #1527541

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

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 high throughput 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.

Recent News

  • Tutorial at the Web Conference “Subgraph counting: the methods behind the madness” May 15, 2019
  • “Parallel Streaming Random Sampling” accepted to Europar 2019 May 8, 2019
  • “Incremental Maintenance of Maximal Cliques in a Dynamic Graph” accepted to the VLDB Journal April 2, 2019
  • Congrats, Dr. Apurba Das March 15, 2019
  • “Weighted Reservoir Sampling from Distributed Streams” accepted to PODS 2019 March 11, 2019
  • Tutorial on Subgraph Counting at The Web Conference 2019 February 12, 2019
  • “Stratified Random Sampling over Streaming and Stored Data” accepted to EDBT 2019 November 26, 2018
  • “Enumerating Top-k Quasi-Cliques” accepted to IEEE Bigdata 2018 October 22, 2018
  • “Shared-Memory Parallel Maximal Clique Enumeration” accepted to HiPC 2018 September 9, 2018
  • “Variance-Reduced Stochastic Gradient Descent on Streaming Data” accepted to NIPS 2018 September 7, 2018

Copyright © 2021 · Iowa State University of Science and Technology. All rights reserved. · Log in