AG-Index: Adjacent Edge Hash Index for Graph Databases
Hui Hui Wang, Yun Feng Peng, He Huang · Applied Mechanics and Materials · 2014
Many queries have been proposed to retrieve graphs. Among others, subgraph query is a fundamental one: given a graph database and a query graph, find the graphs in the database containing the query graph. Most existing works follow the filtering-and-verification framework, where a core task is to reduce the number of candidate graphs. This paper follows the framework and we propose a novel index, namely AG-Index. It indexes adjacent edge pairs of data graphs and can significantly reduce the number of candidate graphs. Our experiments show that our AG-Index outperforms several existing techniques on real-life datasets and synthetic datasets.