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:20210402T160554Z
LOCATION:Track 4
DTSTART;TZID=America/New_York:20201111T154000
DTEND;TZID=America/New_York:20201111T160000
UID:submissions.supercomputing.org_SC20_sess201_ws_ia109@linklings.com
SUMMARY:Labeled Triangle Indexing for Efficiency Gains in Distributed Inte
 ractive Subgraph Search
DESCRIPTION:Workshop\n\nLabeled Triangle Indexing for Efficiency Gains in 
 Distributed Interactive Subgraph Search\n\nReza, Ripeanu, Sanders, Pearce\
 n\nSubgraph search in a massive background graph, i.e., pattern matching i
 n graphs, is a challenging problem, particularly in an interactive usage s
 cenario where fast response time is important.  Our approach, PruneJuice, 
 is based on two intuitions: rather than directly searching for individual 
 matches, it is cheaper to eliminate vertices and edges of the background g
 raph that do not participate in any match. Second, to perform this pruning
  process,  it is possible to decompose a search pattern into a set of cons
 traints, and uses each of these constraints to eliminate non-matching vert
 ices and edges.  This paper explores the feasibility of indexing the backg
 round graph to accelerate the checking  of non-local constraints (e.g., cy
 cles and paths), the most expensive phase of pruning. \n\nIn particular, w
 e demonstrate that indexing labeled triangle (i.e., a 3-Cycle) participati
 on is a valuable acceleration technique. Additionally, we observe that lab
 eled triangle counts at edges can be employed to detect 3-Paths that have 
 terminal points with non-unique labels, at relatively little extra cost. S
 uch paths and triangles are basic sub-constraints that can be used to rapi
 dly prune non-matching vertices and edges. As proof of concept, we show th
 at, using triangle information alone, indexing further accelerates expensi
 ve queries in PruneJuice by up to 500x on billion-edge graphs.\n\nRegistra
 tion Category: Workshop Reg Pass
END:VEVENT
END:VCALENDAR