BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:America/New_York
X-LIC-LOCATION:America/New_York
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20210402T160105Z
LOCATION:Track 3
DTSTART;TZID=America/New_York:20201119T153000
DTEND;TZID=America/New_York:20201119T160000
UID:submissions.supercomputing.org_SC20_sess160_pap119@linklings.com
SUMMARY:GraphPi: High Performance Graph Pattern Matching through Effective
  Redundancy Elimination
DESCRIPTION:Paper\n\nGraphPi: High Performance Graph Pattern Matching thro
 ugh Effective Redundancy Elimination\n\nShi, Zhai, Xu, Zhai\n\nGraph patte
 rn matching, which aims to discover structural patterns in graphs, is cons
 idered one of the most fundamental graph mining problems in real applicati
 ons. Despite previous efforts, existing systems face two main challenges. 
 First, the inherent symmetry existing in patterns can introduce a large am
 ount of redundant computation. Second, different matching orders for a pat
 tern have significant performance differences.\n\nTo address these challen
 ges, we propose GraphPi, a high performance distributed pattern matching s
 ystem. GraphPi utilizes a new algorithm based on 2-cycles that outputs mul
 tiple sets of asymmetric restrictions; each set eliminates redundancy comp
 letely. We also design an accurate performance model to select the optimal
  matching order and asymmetric restriction set for efficient pattern match
 ing. We evaluate GraphPi on Tianhe-2A supercomputer. Results show that Gra
 phPi outperforms the state-of-the-art system by up to 105x with 6 real-wor
 ld graph datasets on a single node. We also scale GraphPi to 1024 computin
 g nodes.\n\nTag: Graph Algorithms, Scalable Computing\n\nRegistration Cate
 gory: Tech Program Reg Pass
END:VEVENT
END:VCALENDAR