Speeding Up Subgraph Matching Queries with Schema Guided Index
Yating Zhao, Wenhan Wang, Shuxin Chen, Bocheng Zhang, Jiajun Wang, Zhaokang Wang · 2024
The performance optimization of existing subgraph matching methods mainly focuses on the topological structure of graphs, with little consideration of the rich schema information provided by complex graphs. This work proposes a Schema Guided Index (SGI) to speed up subgraph matching by utilizing the multiplicity of edge labels provided by the graph schema. SGI presents a DFS-based algorithm to extract many-to-one index paths in the schema and adds extra index edges to graph datasets according to index paths. SGI simplifies query graphs with index edges to reduce computation costs during matching. Experimental results on the LDBC SNB datasets demonstrate that the construction costs of SGI increase near-linearly with the number of edges in the datasets. SGI can reduce the average query response time by up to 36.0%.