Presentation
Pattern Matching on Massive Metadata Graphs at Scale
Author
Advisor
Event Type
Doctoral Showcase
W
TUT
TP
EX
EXH
TimeWednesday, November 14th8:30am - 5pm
LocationC2/3/4 Ballroom
DescriptionPattern matching is a powerful graph analysis tool. Unfortunately, existing solutions have limited scalability, support only a limited set of patterns, and/or focus on only a subset of the real-world problems associated with pattern matching. First, we present a new algorithmic pipeline based on graph pruning that: (i) enables highly scalable exact pattern matching on labeled graphs, (ii) supports arbitrary patterns, (iii) enables trade-offs between precision and time-to-solution, and (iv) supports a set of popular analytics scenarios. We implement our approach on top of HavoqGT and demonstrate its advantages through strong and weak scaling experiments on massive-scale real-world (up to 257B edges) and synthetic (up to 4.4T edges) graphs, respectively, and at scales (1,024 nodes / 36,864 cores) orders of magnitude larger than used in the past for similar problems. Furthermore, we explore avenues to enable approximate matching within the graph pruning model, targeting contemporary and emerging high-impact, real-world applications.
Archive