The Library
Subgraph querying with parallel use of query rewritings and alternative algorithms
Tools
Katsarou, F., Ntarmos, N. and Triantafillou, Peter (2017) Subgraph querying with parallel use of query rewritings and alternative algorithms. In: 20th International Conference on Extending Database Technology, Venice, 21-24 Mar 2017. Published in: 20th International Conference on Extending Database Technology pp. 25-36. ISBN 9783893180738.
An open access version can be found in:
Official URL: http://doi.org/10.5441/002/edbt.2017.04
Abstract
Subgraph queries are central to graph analytics and graph
DBs. We analyze this problem and present key novel discoveries
and observations on the nature of the problem which
hold across query sizes, datasets, and top-performing algorithms.
Firstly, we show that algorithms (for both the decision
and matching versions of the problem) suffer from
straggler queries, which dominate query workload times. As
related research caps query times not reporting results for
queries exceeding the cap, this can lead to erroneous conclusions
of the methods’ relative performance. Secondly, we
study and show the dramatic effect that isomorphic graph
queries can have on query times. Thirdly, we show that
for each query, isomorphic queries based on proposed query
rewritings can introduce large performance benefits. Fourthly,
that straggler queries are largely algorithm-specific: many
challenging queries to one algorithm can be executed effi-
ciently by another. Finally, the above discoveries naturally
lead to the derivation of a novel framework for subgraph
query processing. The central idea is to employ parallelism
in a novel way, whereby parallel matching/decision attempts
are initiated, each using a query rewriting and/or an alternate
algorithm. The framework is shown to be highly beneficial
across algorithms and datasets.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | 20th International Conference on Extending Database Technology | ||||
Publisher: | EDBT | ||||
ISBN: | 9783893180738 | ||||
Official Date: | 21 March 2017 | ||||
Dates: |
|
||||
Page Range: | pp. 25-36 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Open Access (Creative Commons) | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 20th International Conference on Extending Database Technology | ||||
Type of Event: | Conference | ||||
Location of Event: | Venice | ||||
Date(s) of Event: | 21-24 Mar 2017 | ||||
Related URLs: | |||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |