AG-Index: Adjacent edge hash index for graph databases

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. © 2014 Trans Tech Publications, Switzerland.