CRII: SHF: Expediting Subgraph Matching on GPUs

CRII：SHF：加快 GPU 上的子图匹配

• 批准号: 1850274
• 负责人: Hang Liu
• 金额: $ 17.5万
• 依托单位: University of Massachusetts Lowell
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-02-15 至 2019-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1850274&HistoricalAwards=false
• 关键词: CRII; SHF; Expediting; Subgraph; Matching

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.

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