The Library
Hybrid algorithms for subgraph pattern queries in graph databases
Tools
Katsarou, F., Ntarmos, N. and Triantafillou, Peter (2018) Hybrid algorithms for subgraph pattern queries in graph databases. In: 2017 IEEE International Conference on Big Data (IEEE BigData 2017), Boston, MA, USA, 11-14 Dec 2017. Published in: 2017 IEEE International Conference on Big Data (Big Data) ISBN 9781538627167. doi:10.1109/BigData.2017.8257981
|
PDF
WRAP-hybrid-algorithms-subgraph-pattern-queries-graph-databases-Triantafillou-2017.pdf - Accepted Version - Requires a PDF viewer. Download (774Kb) | Preview |
Official URL: https://doi.org/10.1109/BigData.2017.8257981
Abstract
Numerous methods have been proposed over the years for subgraph query processing, as it is central to graph analytics. Existing work is fragmented into two major categories. Methods in the filter-then-verify (FTV) category first construct an index of the DB graphs. Given a query, the index is used to filter out graphs that cannot contain the query. On the remaining graphs, a subgraph isomorphism algorithm is applied to verify whether each graph indeed contains the query. A second category of algorithms is mainly concerned with optimizing the Subgraph Isomorphism (SI) testing process (an NP-Complete problem) in order to find all occurrences of the query within each DB graph, also known as the matching problem. The current research trend is to totally dismiss FTV methods, because SI methods have been shown to enjoy much shorter query execution times and because of the alleged high costs of managing the DB graph index in FTV methods. Thus, a number of new SI methods are being proposed annually. In the current work, we initially study the performance of the latest SI algorithms over datasets consisting of a large number of graphs. With our study, we evaluate the algorithms’ performance and we provide comparison details with former studies. As a second step, we combine the powerful filtering of a top-performing FTV method, with the various SI methods, which leads to the best practice conclusion that SI and FTV shouldn’t be thought of as disjoint types of solutions, as their union achieves better results than any one of them individually. Specifically, we experimentally analyze and quantify the (positive) impact of including the essence of indexed FTV methods within SI methods, showing that query processing times can be significantly improved at modest additional memory costs. We show that these results hold over a variety of well-known SI methods and across several real and synthetic datasets. As such, hybrids of the type reveal a missing opportunity and a blind spot in related literature and trends.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Querying (Computer science), Isomorphisms (Mathematics) | ||||||
Journal or Publication Title: | 2017 IEEE International Conference on Big Data (Big Data) | ||||||
Publisher: | IEEE | ||||||
ISBN: | 9781538627167 | ||||||
Official Date: | 15 January 2018 | ||||||
Dates: |
|
||||||
DOI: | 10.1109/BigData.2017.8257981 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 4 December 2017 | ||||||
Date of first compliant Open Access: | 4 December 2017 | ||||||
RIOXX Funder/Project Grant: |
|
||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | 2017 IEEE International Conference on Big Data (IEEE BigData 2017) | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Boston, MA, USA | ||||||
Date(s) of Event: | 11-14 Dec 2017 | ||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year