=Paper=
{{Paper
|id=Vol-1810/GraphQ_paper_07
|storemode=property
|title=Towards Hybrid Methods for Graph Pattern Queries
|pdfUrl=https://ceur-ws.org/Vol-1810/GraphQ_paper_07.pdf
|volume=Vol-1810
|authors=Foteini Katsarou,Nikos Ntarmos,Peter Triantafillou
|dblpUrl=https://dblp.org/rec/conf/edbt/KatsarouNT17a
}}
==Towards Hybrid Methods for Graph Pattern Queries==
https://ceur-ws.org/Vol-1810/GraphQ_paper_07.pdf
Towards Hybrid Methods for Graph Pattern Queries
Foteini Katsarou Nikos Ntarmos Peter Triantafillou
School of Computing Science School of Computing Science School of Computing Science
University of Glasgow, UK University of Glasgow, UK University of Glasgow, UK
f.katsarou.1@ nikos.ntarmos@ peter.triantafillou@
research.gla.ac.uk glasgow.ac.uk glasgow.ac.uk
ABSTRACT graph is contained in each graph and/or find all its occur-
In the subgraph querying problem, given a query graph and rences within a larger stored graph. Subgraph querying
a dataset of graphs, we want to locate which graphs in the entails the subgraph isomorphism problem (abbreviated as
dataset contain the query and/or find all its occurrences. sub-iso), which is known to be NP-complete. Over the years,
Over the years, numerous methods, fragmented in 2 cate- subgraph querying has received a lot of attention which is
gories, were proposed to tackle the problem. In the first cat- evident by the numerous proposed methods. Related work
egory, methods follow the filter-then-verify (FTV) paradigm is categorized in 2 major categories: the filter-then-verify
where an index is used to filter out graphs that definitely do (FTV) methods and the no-filter, verify (NFV) methods.
not contain the query as an answer. On the remaining set Various recent experimental analysis papers (e.g. [2, 3, 1])
of graphs, a subgraph isomorphism algorithm is applied to compare and stress-test the proposed methods and provide
verify the graphs that contain the query graph. A second interesting insights about the performance of both FTV and
category, so called no-filter, verify (NFV), invested in opti- NFV methods.
mizing the subgraph isomorphism process, by employing a
lightweight index primarily to locate candidate vertices on 2. APPROACH, RESULT OVERVIEW, AND
the graphs in the dataset. The current trend is to totally dis- CONCLUSIONS
miss the FTV methods and employ NFV methods instead.
The latest works, e.g. [3], tend to dismiss the FTV meth-
With this work we wish to point out that a hybrid solution
ods with the claim that the fast sub-iso test of the NFV
that is, a combination of the filtering of some FTV method
methods significantly outperforms the index-based scan of
with the subgraph isomorphism test of top-performing NFV
the FTV methods. In the current work, we put forth our
methods, can be highly competitive in terms of performance
concern about the possibility that lots of current state of
vis-a-vis methods from either the FTV or the NFV category.
the art and on-going efforts miss a potential for deriving
We will present some preliminary results, based on experi-
highly performant algorithms by investigating hybrid solu-
ments, where such a combination proves to be beneficial by
tions which maintain the filtering of the FTV and the much
primarily avoiding the initiation of a large number of redun-
faster sub-iso test algorithms of the NFV methods. Based
dant subgraph isomorphism tests.
on our initial experiments, this design option can introduce
very significant performance gains in the subgraph match-
Keywords ing problem. Essentially, the benefits stem from using the
FTV-style indexes in order to avoid the need to perform the
Graph databases, graph query processing, subgraph isomor-
sub-iso test on a large majority of the graphs in the graph
phism
DB. And the benefits are large both against FTV and NFV
methods alone.
1. INTRODUCTION
Graphs are ideal for representing complex entities as they 3. REFERENCES
physically incorporate relationships/interactions in the form [1] F. Katsarou, N. Ntarmos, and P. Triantafillou.
of edges. Revealing the existence of a pattern graph in vari- Subgraph Querying with Parallel Use of Query
ous graphs/parts of the same graph is essential to graph an- Rewritings and Alternative Algorithms. In EDBT, ’17.
alytics. In subgraph querying, given a pattern graph (query) [2] F. Katsarou, N. Ntarmos, and P. Triantafillou.
and a dataset of graphs, we want to know whether the query Performance and scalability of indexed subgraph query
processing methods. PVLDB, 8(12):1566–1577, 2015.
[3] J. Lee, W.-S. Han, R. Kasperovics, and J.-H. Lee. An
in-depth comparison of subgraph isomorphism
algorithms in graph databases. PVLDB, 6(2), 2012.
c 2017, Copyright is with the authors. Published in the Workshop Pro-
ceedings of the EDBT/ICDT 2017 Joint Conference (March 21, 2017,
Venice, Italy) on CEUR-WS.org (ISSN 1613-0073). Distribution of this
paper is permitted under the terms of the Creative Commons license CC-
by-nc-nd 4.0