CRII: SHF: Expediting Subgraph Matching on GPUs

我们生活在一个联系日益紧密的世界里，大数据运动不仅带来了更多的数据，更重要的是，带来了更多的连接数据，比如社交网络、知识图谱和深度神经网络。子图同构，从一个巨大的数据图中找到感兴趣的子图，是一系列关键应用的基本工具，例如，网络安全，犯罪侦查和医疗保健。尽管有如此巨大的潜力，但是在大数据环境下，由于计算复杂度和内存消耗高，识别所有同构子图是一个挑战。该项目解决了这一问题，并将有利于工业界和学术界，以及培养本科生，代表性不足和STEM高中学生进行高性能数据分析（HPDA）研究（https://www.uml.edu/research/hpda/）.Conventional)，努力将查询图分成两个不相交的部分进行修剪和连接，这削弱了查询图的修剪强度，并导致大量没有希望的候选对象进入“连接”阶段。这个项目提倡一种完整的基于查询图的修剪方法来解决计算和内存方面的挑战。具体而言，本研究包括两个部分：1)算法研究——基于来源感知的交叉点候选构建——将大大减少传统方法面临的误报；2)系统研究，即GPU支持的大规模并行源群交叉，将通过使用图形处理单元（GPU）加速来解决传统CPU平台上遇到的瓶颈。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

We are living in an increasingly connected world, where the Big Data movement has resulted in not only more data but, more importantly, more connected data, such as, social networks, knowledge graphs and deep neural networks. Sub-graph isomorphism, which finds sub-graphs of interest from an enormous data graph, is a fundamental tool for an array of critical applications, e.g., cyber-security, criminal detection and health care. In spite of such a great potential, identifying all isomorphic sub-graphs is a challenge in the Big Data context due to high computation complexity and memory consumption. This project addresses this issue, and will benefit both industrial and academic communities, as well as train undergraduate, underrepresented and STEM high school students for high-performance data analytics (HPDA) research (https://www.uml.edu/research/hpda/).Conventional efforts split the query graph into two disjoint parts for prune and join, which impairs the prune strength of the query graph and results in a large volume of unpromising candidates for the 'join' phase. This project advocates an entire query graph-based prune approach to resolve the computation and memory challenge. In particular, this research consists of two parts: 1) algorithms research -- provenance-aware intersection-based candidate construction -- will greatly reduce the false positives faced by the conventional approaches; 2) systems research, i.e., GPU-enabled massively parallel provenance group intersection, will tackle the bottleneck that is encountered on conventional CPU platforms, through use of Graph Processing Unit (GPU) acceleration.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.