초록

용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

In this paper, we study the subgraph matching problem in a large database graph, which finds all subgraphs in the database graph that are isomorphic to a query graph. Recently, feature index-based methods have been proposed for fast subgraph matching in a large database graph. They adopt the concept...

In this paper, we study the subgraph matching problem in a large database graph, which finds all subgraphs in the database graph that are isomorphic to a query graph. Recently, feature index-based methods have been proposed for fast subgraph matching in a large database graph. They adopt the concept of vertex features to easily compare the vertices from a database graph with those from a query graph and filter out vertices in the database graph not eligible for subgraph matching. Previous approaches use various kinds of vertex features such as label distribution and discriminative substructures. However, they do not carefully consider the tradeoff between pruning power and extraction cost of vertex features. In this paper we propose a feature index called F-Index for fast subgraph matching. F-Index strikes a balance between pruning power and extraction cost. It uses the combination of label distribution and connectivity information of neighbors as vertex features. F-Index is constructed over the extracted vertex features for fast filtering of unqualified vertices. Experimental results show that our method outperforms the existing methods in terms of query processing time with comparable index build time.

주제어