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:20181221T160728Z
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:Workshop\nArchitectures, Data Analytics, Graph Algorithms, Wor
 kshop Reg Pass\n\nThere Are Trillions of Little Forks in the Road:  Choose
  Wisely! -- Estimating the Cost and Likelihood of Success of Constrained W
 alks to Optimize a Graph Pruning Pipeline\n\nTripoul, Halawa, Reza, Sander
 s, Pearce...\n\nWe have developed [Reza et al. SC18] a highly scalable alg
 orithmic pipeline for pattern matching in labeled graphs and demonstrated 
 it on trillion-edge graphs. This pipeline: (i) supports arbitrary search p
 atterns, (ii) identifies all the vertices and edges that participate in ma
 tches - offering 100% precision and recall, and (iii) supports realistic d
 ata analytics scenarios. This pipeline is based on graph pruning: it decom
 poses the search template into individual constraints and uses them to rep
 eatedly prune the graph to a final solution.\n\nOur current solution, howe
 ver, makes a number of ad-hoc intuition-based decisions with impact on per
 formance. 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 position paper makes the observation that by estimating the runtime
  cost and likelihood of success of a constrained walk in a labeled graph o
 ne can inform these optimization decisions. We propose a preliminary solut
 ion to make these estimates, and demonstrate - using a prototype shared-me
 mory implementation - that this: (i) is feasible with low overheads, and (
 ii) offers accurate enough information to optimize our pruning pipeline by
  a significant margin.
URL:https://sc18.supercomputing.org/presentation/?id=ws_ia116&sess=sess168
END:VEVENT
END:VCALENDAR