A budget-based algorithm for efficient subgraph matching on huge networks

Matthias Bröcheler*, Andrea Pugliese, V. S. Subrahmanian

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

As social network and RDF data grow dramatically in size to billions of edges, the ability to scalably answer queries posed over graph datasets becomes increasingly important. In this paper, we consider subgraph matching queries which are often posed to social networks and RDF databases - for such queries, we want to find all matching instances in a graph database. Past work on subgraph matching queries uses static cost models which can be very inaccurate due to long-tailed degree distributions commonly found in real world networks. We propose the BudgetMatch query answering algorithm. BudgetMatch costs and recosts query parts adaptively as it executes and learns more about the search space. We show that using this strategy, BudgetMatch can quickly answer complex subgraph queries on very large graph data. Specifically, on a real world social media data set consisting of 1.12 billion edges, we can answer complex subgraph queries in under one second and significantly outperform existing subgraph matching algorithms.

Original languageEnglish (US)
Title of host publicationICDE Workshops 2011 - 2011 IEEE 27th International Conference on Data Engineering Workshops
Pages94-99
Number of pages6
DOIs
StatePublished - 2011
Externally publishedYes
Event2011 IEEE 27th International Conference on Data Engineering Workshops, ICDE 2011 - Hannover, Germany
Duration: Apr 11 2011Apr 16 2011

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627

Conference

Conference2011 IEEE 27th International Conference on Data Engineering Workshops, ICDE 2011
Country/TerritoryGermany
CityHannover
Period4/11/114/16/11

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Information Systems

Fingerprint

Dive into the research topics of 'A budget-based algorithm for efficient subgraph matching on huge networks'. Together they form a unique fingerprint.

Cite this