TY - GEN
T1 - A budget-based algorithm for efficient subgraph matching on huge networks
AU - Bröcheler, Matthias
AU - Pugliese, Andrea
AU - Subrahmanian, V. S.
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=79958040133&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79958040133&partnerID=8YFLogxK
U2 - 10.1109/ICDEW.2011.5767618
DO - 10.1109/ICDEW.2011.5767618
M3 - Conference contribution
AN - SCOPUS:79958040133
SN - 9781424491940
T3 - Proceedings - International Conference on Data Engineering
SP - 94
EP - 99
BT - ICDE Workshops 2011 - 2011 IEEE 27th International Conference on Data Engineering Workshops
T2 - 2011 IEEE 27th International Conference on Data Engineering Workshops, ICDE 2011
Y2 - 11 April 2011 through 16 April 2011
ER -