2020 Virtual undergraduate Research symposium

IncMine – Fast Incremental Graph Computation


PROJECT NUMBER: 44

AUTHOR: Noah Fields, Computer Science | MENTOR: Bo Wu, Computer Science

 

ABSTRACT

Incremental graph mining–finding instances of a subgraph in a large graph that changes in real time–is an important problem in the field of big data. From fraud detection to protein folding, incremental graph mining has many applications. Existing programs are unable to efficiently process changes on large graphs, only capable of batch mining (recomputing the entire graph), overly specific (only able to find certain patterns), susceptible to overcounting patterns, or some combination of the above. Here we present a new algorithm which aims to resolve these issues. By using techniques from program synthesis, an optimized algorithm is automatically generated for counting an arbitrary pattern. The synthesized solution enforces a total ordering of edges in the data graph, allowing parallelization and avoiding overcounting. This expands on previous work such as GraphZero, which applied similar techniques for batch mining. Our new algorithm and its associated program represent a significant step forward for incremental graph mining and other forms of graph computation, as it enables larger and more complex patterns to be mined quickly on larger graphs than previously possible. It does this with minimal memory overhead and avoids the need for creating incremental graph algorithms by hand.

 

VISUAL PRESENTATION

 

AUTHOR BIOGRAPHY

Noah Fields is a sophomore in the Computer Science department with a minor in Applied Mathematics and Statistics. His areas of academic interest include algorithmic complexity, caching theory, and abstract math. Over the 2018-2019 semester he worked with professors, PhD students, and other undergrads on IncMine, a powerful tool for incremental graph computation that is unrivaled in its speed.

 


1 Comment

  1. Very clear presentation. Very confident presentation.

Share This