Labelled Triangle Indexing for Efficiency Gains in Distributed Interactive Subgraph Search
Tahsin Arafat Reza · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 2020
Subgraph search in a massive background graph, i.e., pattern matching in graphs, is a challenging problem, particularly in an interactive usage scenario where fast response time is important.Our approach, PruneJuice [1], is based on two intuitions: first, rather than searching for individual matches, PruneJuice iteratively eliminates the vertices and edges of the background graph that do not participate in any match.Second, to perform this pruning process, PruneJuice, decomposes the search patterns in a set of constraints and uses each of these constraints to eliminate vertices and edges.This paper explores the feasibility of indexing the background graph to accelerate the checking non-local constraints (e.g., cycles and paths) the most expensive phase of pruning.In particular, we demonstrate that indexing labeled triangle (3-Cycle) participation is a valuable acceleration technique.Additionally, we observe that labelled triangle counts at edges can be employed to detect 3-Paths that have terminal points with non-unique labels, at relatively little extra cost.Such paths and triangles are basic subconstraints that can be used to rapidly prune non-matching vertices and edges.As proof of concept, we show that using triangle information alone further accelerates expensive queries by up to 500× on billion-edge graphs.