Title :
A budget-based algorithm for efficient subgraph matching on Huge Networks
Author :
Bröcheler, Matthias ; Pugliese, Andrea ; Subrahmanian, V.S.
Author_Institution :
Univ. of Maryland, College Park, MD, USA
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.
Keywords :
budgeting; database management systems; social networking (online); BudgetMatch query answering algorithm; RDF database; budget based algorithm; huge network; social media; social network; subgraph matching; Indexes; Motion pictures; Query processing; Radio access networks; Resource description framework; Social network services;
Conference_Titel :
Data Engineering Workshops (ICDEW), 2011 IEEE 27th International Conference on
Conference_Location :
Hannover
Print_ISBN :
978-1-4244-9195-7
Electronic_ISBN :
978-1-4244-9194-0
DOI :
10.1109/ICDEW.2011.5767618