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.
