Graph Indexing and Querying Using Fingerprint of Discriminative Frequent Fragments

Abstract

Graphs are widely used to model complex structured data. Given a graph query, it is desirable to retrieve graphs quickly from a large database via graph-based indices. In this paper, we propose a graph indexing and querying model based on discriminative frequent fragments and fingerprint of these fragments. There are two main steps: index construction and query processing. In index construction phase, edge dictionary is used to simplify the process and to generate ids of graph edges. To reduce the size of index structure, two techniques, size-increasing support constraint and discriminative fragments are used. Canonical codes are then constructed based on discriminative frequent fragments. Then DB fingerprint is built based on codes. In query processing phase, query graph is parsed and canonical codes are constructed. Query’s codes and DB fingerprint’s codes are compared to get candidate answer set. Finally, candidate answer set is verified to ensure the query graph really contains in it or not by performing simple subgraph isomorphism test on each graph one by one.