Ensuring Consistency in Graph Cache for Graph-Pattern Queries
Jing Wang, Nikos Ntarmos, Peter Triantafillou · ENLIGHTEN (Jurnal Bimbingan dan Konseling Islam) · 2017
Graph queries are costly, as they entail the NP-Complete subgraph isomorphism problem. Graph caching had been recently suggested, showing the potential to significantly accelerate subgraph/supergraph queries. Subsequently, Graph- Cache, the first full-fledged graph caching system was put forth. However, when the underlying dataset changes con- currently with the query workload proceeding, how to ensure the graph cache consistency becomes an issue. The current work provides a systematic solution to address this problem, by presenting an upgraded GraphCache system coined GraphCache+ (abbreviated as GC+). We develop two GC+ exclusive models that employ different approaches to deal with the consistency issue. Moreover, we present the logic of GC+ in expediting queries, bundled with the formally proved correctness. We evaluate the performance of GC+ by a real-world graph dataset and a number of query workloads with different characteristics, highlighting the considerable speedup in term of quantified benefit and overhead.