Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Performance and scalability of indexed subgraph query processing methods

Tools
- Tools
+ Tools

Triantafillou, Peter (2016) Performance and scalability of indexed subgraph query processing methods. In: ALGOCLOUD 2015, Greece., 14–15 Sep 2016. Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 9511

Research output not available from this repository, contact author.
Official URL: https://link.springer.com/content/pdf/bfm%3A978-3-...

Request Changes to record.

Abstract

Graph data management systems have become very popular, as graphs are the natural data model for many applications. One of the main problems addressed by these systems is subgraph query processing; i.e., given a query graph, return all graphs that contain the query. The naive method for processing such queries is to perform a subgraph isomorphism test against each graph in the dataset. This obviously does not scale, as subgraph isomorphism is NP-complete. Thus, many indexing methods have been proposed to reduce the number of candidate graphs that have to underpass the subgraph isomorphism test. In this tutorial, we identify a set of key factors–parameters that influence the performance of related methods: namely, the number of nodes per graph, the graph density, the number of distinct labels, the number of graphs in the dataset, and the query graph size. We then discuss comprehensive and systematic experiments that analyze the sensitivity of the various methods on the values of the key parameters. Our aims are twofold: first to draw conclusions about the relative performance of the algorithms, and, second, to stress-test all algorithms, deriving insights as to their scalability and highlighting how both performance and scalability depend on these factors. We present six well-established indexing methods, namely, Grapes, CT-Index, GraphGrepSX, gIndex, Tree+, and gCode, as representative approaches of the overall design space, including the most recent and best-performing methods. We report on their index construction time and index size as well as on query processing performance in terms of time and false-positive ratio. We discuss performance on both real and synthetic datasets. Specifically, four real datasets of different characteristics are used: AIDS, PDBS, PCM, and PPI. In addition, we report on a large number of synthetic graph datasets, empowering us to systematically study the performance and scalability of the algorithms as they depend on the aforementioned key parameters. © Springer International Publishing Switzerland 2016.

Item Type: Conference Item (Paper)
Divisions: Faculty of Science > Computer Science
Series Name: Lecture Notes in Computer Science
Journal or Publication Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher: Springer
Book Title: Algorithmic Aspects of Cloud Computing
Official Date: September 2016
Dates:
DateEvent
September 2016Published
Volume: 9511
Status: Peer Reviewed
Publication Status: Published
Publisher Statement: cited By 0
Conference Paper Type: Paper
Title of Event: ALGOCLOUD 2015
Type of Event: Conference
Location of Event: Greece.
Date(s) of Event: 14–15 Sep 2016
Related URLs:
  • Other

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us