RNET TECHNOLOGIES INC — Department of Defense SBIR Phase I: SB151-004

Description

The importance of graph applications is growing as society becomes more interconnected. Many real world datasets are best modeled as graphs, e.g., road networks, the Internet, social networks, protein-protein interactions, utility grids, and communication. Graph analytics are used to answer many different categories of questions, including traversal, querying, and data mining. It is often desirable to execute graph analytics applications on a wide range of hardware platforms (from supercomputers to mobile devices).The fundamental question we will explore include: Can a small set of high-level graph/matrix operations be identified and implemented, to enable high performance, high user productivity, and performance portability for a wide range of graph analytics applications of interest to the DoD, with effectiveness on a diverse collection of data setsThe equivalence between a graph and the associated sparse matrix encoding a graph's adjacency list has prompted considerable interest in casting various graph algorithms in terms of sparse matrix operations.We propose to identify a set of high-level matrix and graph operations, create efficient implementations for multiple platforms (using multiple algorithms/representations to optimize for data-set dependence), and demonstrate their effectiveness on a range of graph analytics applications.