Many-Core Acceleration of Common Graph Programming Frameworks

Graphs are an exceptional data structure for representing knowledge and relationships between facts. There are various frameworks for creating, modifying, and traversing graphs in software. These frameworks provide an abstraction over the physical representation of graphs on disk. Usually, the graphs are modeled physically as tables. The schema or layout of these tables significantly impacts the performance of graph traversals. Our project seeks to improve the manner in which these tables are represented to get significant speeds in graph traversals. Recent research has shown shredding adjacency list across columns results in better performance over common vertical representations because the sizes of the tables are more compact with shredding. We intend to extend this work with an approach we created for localizing subgraphs with similar topology and logical properties using indexes created dynamically. By deploying our approach on high performance computing platforms, such as general purpose graphic processing units (GPGPU) we expect to get significant speeds up over current approaches. For this project, we will create a proof-of-concept based on a solid mathematical theory of our approach. We will analyze the complexity of our approach mathematically and experimentally based on test data that reflects DoD use cases.