The Library
Indexing query graphs to speedup graph query processing
Tools
Wang, Jing, Ntarmos, Nikos and Triantafillou, Peter (2016) Indexing query graphs to speedup graph query processing. In: EDBT : 19th International Conference on Extending Database Technology, Bordeaux, France , 15-18 Mar 2016. Published in: Advances in database technology - EDBT 2016 19th International Conference on Extending Database Technology, Bordeaux, France, March 15-18, 2016 : proceedings pp. 41-52. ISBN 9783893180707 .
|
PDF
WRAP-indexing-query-graphs-query-processing-Triantaffillou-2017.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (2693Kb) | Preview |
Official URL: http://www.worldcat.org/oclc/957156764
Abstract
Subgraph/supergraph queries although central to graph analytics, are costly as they entail the NP-Complete problem of subgraph isomorphism. We present a fresh solution, the novel principle of which is to acquire and utilize knowledge from the results of previously executed queries. Our approach, iGQ, encompasses two component subindexes to identify if a new query is a subgraph/supergraph of previously executed queries and stores related key information. iGQ comes with novel query processing and index space management algorithms, including graph replacement policies. The end result is a system that leads to significant reduction in the number of required subgraph isomorphism tests and speedups in query processing time. iGQ can be incorporated into any sub/supergraph query processing method and help improve performance. In fact, it is the only contribution that can speedup significantly both subgraph and supergraph query processing. We establish the principles of iGQ and formally prove its correctness. We have implemented iGQ and have incorporated it within three popular recent state of the art index-based graph query processing solutions. We evaluated its performance using real-world and synthetic graph datasets with different characteristics, and a number of query workloads, showcasing its benefits.
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), Graph algorithms, Data mining, Database management | ||||||
Journal or Publication Title: | Advances in database technology - EDBT 2016 19th International Conference on Extending Database Technology, Bordeaux, France, March 15-18, 2016 : proceedings | ||||||
Publisher: | Konstanz University of Konstanz, University Library | ||||||
ISBN: | 9783893180707 | ||||||
Official Date: | 2016 | ||||||
Dates: |
|
||||||
Page Range: | pp. 41-52 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Date of first compliant deposit: | 1 December 2017 | ||||||
Date of first compliant Open Access: | 5 December 2017 | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | EDBT : 19th International Conference on Extending Database Technology | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Bordeaux, France | ||||||
Date(s) of Event: | 15-18 Mar 2016 | ||||||
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