CodeTreesub: Efficient subgraph search with graph code indices and its comprehensive performance evaluation

This paper describes a highly efficient method for the subgraph search problem, a fundamental issue in database query processing. The proposed CodeTreesub extends the existing CodeTree method from a supergraph search technique to a subgraph search method. Importantly, CodeTreesub is an index-based approach, despite assertions that the use of indices for the subgraph search problem is inherently inefficient. The proposed method has three advantages over existing techniques. First, unlike existing index-based methods, which extract numerous patterns through enumeration or subgraph mining, CodeTreesub uses relatively few patterns extracted at random from all available patterns. This significantly reduces the time required to construct the index. Second, rather than simple path and cycle patterns, CodeTreesub uses the more complex induced subgraphs as patterns, which enables excellent filtering performance from few patterns. Third, by searching for solutions during the filtering step, the need to verify subgraph isomorphisms is removed. We compare the subgraph search performance of CodeTreesub with existing index- and vertex connectivity approaches, including the state-of-the-art CFQL and VEQS, on seven datasets and ten query tasks. The experimental evaluations demonstrate that CodeTreesub is at least as fast as CFQL and VEQS in terms of query processing, filtering, and verification, and can be orders of magnitude faster depending on the dataset and search task. Overall, the results from this study highlight the potential of index-based methods to achieve efficient subgraph search outcomes.