CRII: SHF: Expediting Subgraph Matching on GPUs

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

• 批准号: 2331536
• 负责人: Hang Liu
• 金额: $ 17.5万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-01-01 至 2025-01-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2331536&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/).Conventional努力将查询图拆分为两个互不相交的部分用于修剪和连接，这会削弱查询图的修剪强度，并导致大量没有希望的候选对象进入“连接”阶段。该项目倡导一种完整的基于查询图的剪枝方法来解决计算和存储挑战。具体地说，这项研究包括两部分：1)算法研究--基于起源感知的交叉点候选构建--将极大地减少传统方法面临的误报；2)系统研究，即启用GPU的大规模并行源组交叉点，将通过使用图形处理单元(GPU)加速来解决在传统CPU平台上遇到的瓶颈。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。