CRII: SHF: Expediting Subgraph Matching on GPUs

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

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.