The Library
Towards hybrid methods for graph pattern queries
Tools
Tools
Tools
Katsarou, F., Ntarmos, N. and Triantafillou, Peter (2017) Towards hybrid methods for graph pattern queries. In: EDBT/ICDT 2017 Joint Conference, Venice, Italy, 21 Mar 2017. Published in: CEUR Workshop Proceedings, 1810 ISSN 1613-0073.
Research output not available from this repository, contact author.
Official URL: https://www.scopus.com/inward/record.uri?eid=2-s2....
Abstract
In the subgraph querying problem, given a query graph and a dataset of graphs, we want to locate which graphs in the dataset contain the query and/or find all its occurrences. Over the years, numerous methods, fragmented in 2 categories, were proposed to tackle the problem. In the first category, methods follow the filter-then-verify (FTV) paradigm where an index is used to filter out graphs that definitely do not contain the query as an answer. On the remaining set of graphs, a subgraph isomorphism algorithm is applied to verify the graphs that contain the query graph. A second category, so called no-filter, verify (NFV), invested in optimizing the subgraph isomorphism process, by employing a lightweight index primarily to locate candidate vertices on the graphs in the dataset. The current trend is to totally dismiss the FTV methods and employ NFV methods instead. With this work we wish to point out that a hybrid solution that is, a combination of the filtering of some FTV method with the subgraph isomorphism test of top-performing NFV methods, can be highly competitive in terms of performance vis-a-vis methods from either the FTV or the NFV category. We will present some preliminary results, based on experiments, where such a combination proves to be beneficial by primarily avoiding the initiation of a large number of redundant subgraph isomorphism tests. © 2017, Copyright is with the authors.
| Item Type: | Conference Item (Paper) | ||||
|---|---|---|---|---|---|
| Divisions: | Faculty of Science > Computer Science | ||||
| Journal or Publication Title: | CEUR Workshop Proceedings | ||||
| Publisher: | Sun SITE Central Europe | ||||
| ISSN: | 1613-0073 | ||||
| Official Date: | 2017 | ||||
| Dates: |
|
||||
| Volume: | 1810 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Publisher Statement: | cited By 0 | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Conference Paper Type: | Paper | ||||
| Title of Event: | EDBT/ICDT 2017 Joint Conference | ||||
| Type of Event: | Conference | ||||
| Location of Event: | Venice, Italy | ||||
| Date(s) of Event: | 21 Mar 2017 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
