Title: Indexing Graph Databases for Graph Containment Search

Author: Dayu Yuan, Prasenjit Mitra

Graph containment search is a popular search scenario with broad
applications in bioinformatics, chemoinformatics and other scientific
and commercial fields. Given a query graph, the subgraph containment
search algorithm searches over a graph database, returns graphs
containing the query as a subgraph, whereas the supergraph containment
search algorithm returns database graphs contained in the
query. Determining whether a graph g is a subgraph of another is an
NP-complete problem. Hence, it is intractable to compute the graph
containment search online for large graph databases. Graph indices are
commonly used to improve the performance of graph containment search.
Various kinds of subgraph patterns have been proposed to build graph
indices. Each of them works with a specifically designed index
structure, e.g., discriminative and frequent subgraph patterns work
with gIndex, $\delta$-TCFG patterns work with FG-Index, etc. We
propose Lindex, a graph index that indexes subgraph patterns for both
the subgraph and supergraph containment search. Lindex is compatible
with any choice of patterns. Compared to previous works, Lindex is
compact in space and fast in index lookup. Empirically, we demonstrate
that Lindex used in conjunction with subgraph indexing pattern
proposed in previous works outperforms other specifically designed
index structures.