BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:America/Chicago
X-LIC-LOCATION:America/Chicago
BEGIN:DAYLIGHT
TZOFFSETFROM:-0600
TZOFFSETTO:-0500
TZNAME:CDT
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0500
TZOFFSETTO:-0600
TZNAME:CST
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20260522T150118Z
LOCATION:D172
DTSTART;TZID=America/Chicago:20181112T114500
DTEND;TZID=America/Chicago:20181112T121000
UID:submissions.supercomputing.org_SC18_sess168_ws_ia116@linklings.com
SUMMARY:There Are Trillions of Little Forks in the Road:  Choose Wisely! -
 - Estimating the Cost and Likelihood of Success of Constrained Walks to Op
 timize a Graph Pruning Pipeline
DESCRIPTION:Nicolas Tripoul, Hassan Halawa, and Tahsin Reza (University of
  British Columbia); Geoffrey Sanders and Roger Pearce (Lawrence Livermore 
 National Laboratory); and Matei Ripeanu (University of British Columbia)\n
 \nWe have developed [Reza et al. SC18] a highly scalable algorithmic pipel
 ine for pattern matching in labeled graphs and demonstrated it on trillion
 -edge graphs. This pipeline: (i) supports arbitrary search patterns, (ii) 
 identifies all the vertices and edges that participate in matches - offeri
 ng 100% precision and recall, and (iii) supports realistic data analytics 
 scenarios. This pipeline is based on graph pruning: it decomposes the sear
 ch template into individual constraints and uses them to repeatedly prune 
 the graph to a final solution.\n\nOur current solution, however, makes a n
 umber of ad-hoc intuition-based decisions with impact on performance. In a
  nutshell these relate to (i) constraint selection -  which constraints to
  generate? (ii) constraint ordering - in which order to use them? and (iii
 ) individual constraint generation - how to best verify them? This positio
 n paper makes the observation that by estimating the runtime cost and like
 lihood of success of a constrained walk in a labeled graph one can inform 
 these optimization decisions. We propose a preliminary solution to make th
 ese estimates, and demonstrate - using a prototype shared-memory implement
 ation - that this: (i) is feasible with low overheads, and (ii) offers acc
 urate enough information to optimize our pruning pipeline by a significant
  margin.\n\nTag: Architectures, Data Analytics, Graph Algorithms\n\nRegist
 ration Category: Workshop Reg Pass\n\nSession Chairs: Vito Giovanni Castel
 lana (Pacific Northwest National Laboratory (PNNL)), John Feo (Pacific Nor
 thwest National Laboratory (PNNL)), and Antonino Tumeo (Pacific Northwest 
 National Laboratory (PNNL))\n\n
END:VEVENT
END:VCALENDAR