  Streaming graphs are drawing increasing attention in both academic and
industrial communities as many graphs in real applications evolve over time.
Continuous subgraph matching (shorted as CSM) aims to report the incremental
matches of a query graph in such streaming graphs. It involves two major steps,
i.e., candidate maintenance and incremental match generation, to answer CSM.
Throughout the course of continuous subgraph matching, incremental match
generation backtracking over the search space dominates the total cost.
However, most previous approaches focus on developing techniques for efficient
candidate maintenance, while incremental match generation receives less
attention despite its importance in CSM. Aiming to minimize the overall cost,
we propose two techniques to reduce backtrackings in this paper. We present a
cost-effective index CaLiG that yields tighter candidate maintenance, shrinking
the search space of backtracking. In addition, we develop a novel incremental
matching paradigm KSS that decomposes the query vertices into conditional
kernel vertices and shell vertices. With the matches of kernel vertices, the
incremental matches can be produced immediately by joining the candidates of
shell vertices without any backtrackings. Benefiting from reduced
backtrackings, the elapsed time of CSM decreases significantly. Extensive
experiments over real graphs show that our method runs faster than the
state-of-the-art algorithm orders of magnitude.
