Fast Subgraph Search with Graph Code Indices

The subgraph search problem is of fundamental importance in the fields of information science and database management. In this paper, we propose an index-based subgraph search method that is as fast as the current state-of-the-art technique. The proposed method is an extension of CodeTree, which is a supergraph search method that uses neither enumeration nor graph mining. The extended \(\text {CodeTree}_{sub}\) treats graphs as graph codes and uses the prefix tree for these graph codes as an index. This index permits the highly efficient filtering of non-solutions, but its construction entails little computational overhead. \(\text {CodeTree}_{sub}\) effectively limits the number of candidate solutions so that only induced subgraphs of graphs in databases are included in the index, thus accelerating the filtering step. Additionally, \(\text {CodeTree}_{sub}\) can identify some solutions during the filtering stage. The result is a scalable, high-speed graph filtering and verification method. We compared the performance of \(\text {CodeTree}_{sub}\) with that of two non-index-based techniques on six benchmark datasets. The results demonstrated that the proposed method was consistently as fast as or faster than the state-of-the-art \(\text {VEQ}_S\) method in terms of query processing. This study is of particular interest because it illustrates that index-based methods have the potential to outperform non-index-based techniques, thereby providing enhanced query speeds for small- and large-scale databases alike.