A Budget-Based Algorithm for Efficient Subgraph Matching on Huge Networks

In: Conference| Publication

16 Apr 2011

Workshop Paper, ICDE Workshop on Graph Data Management, 2011, Hannover, Germany
Authors: Matthias Broecheler, Andrea Pugliese, VS Subrahmanian
Direct link to paper

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.


Share and Enjoy:
  • Digg
  • del.icio.us
  • Technorati
  • description
  • MisterWong
  • Netvouz
  • ThisNext
  • StumbleUpon

14 Responses to A Budget-Based Algorithm for Efficient Subgraph Matching on Huge Networks



February 12th, 2013 at 12:00 am


Zenegra tadalafil vs sildenafil citrate

November 27th, 2013 at 10:22 pm

rggmelopxmfehfgspnjogpsnbujpo, Tadalafil pulmonary hypertension, spVRdiq, [url=http://seniorcareheroes.com/]Tadalafil net[/url], FrWkxbb, http://seniorcareheroes.com/ What is cialis tadalafil, uzXRLaY.



December 18th, 2013 at 11:06 pm

pLyp2i yvajjrqgdkbs, [url=http://idecptjupxgy.com/]idecptjupxgy[/url], [link=http://dnjvlfdelysy.com/]dnjvlfdelysy[/link], http://fopldozgdfjy.com/


Cheap viagra online

January 1st, 2014 at 8:01 pm

, Cialis generic, 930217, Viagra online, 971, Buy cialis, 60970, Discount viagra online, lbt, Discount cialis, 078408, Generic viagra, 258, Viagra, %-((, Viagra, :-OOO, Online pharmacy, krqogw,


novoline tricks 2012

January 23rd, 2014 at 8:29 am

Hey there! Quick question that’s completely off topic.
Do you know how to make your site mobile friendly?
My blog looks weird when viewing from my apple iphone.

I’m trying to find a template or plugin that might be able to resolve
this problem. If you have any suggestions, please share.
With thanks!



February 9th, 2014 at 3:52 pm



February 9th, 2014 at 4:05 pm

, Cialis, :-]], Viagra, 234, Kamagra, tevx, Sildenafil online, cjel, Viagra, afrsf, Generic cialis online, 8-PPP, Viagra, iuefet, Vardenafil hydrochloride, 824577, Generic viagra, 8((,



February 14th, 2014 at 6:15 am

, Tadacip online, =], Buy cialis online, 893901, Canadian cialis, :-))), Viagra, =-]]], Vigora, =PPP, Viagra, vqsp, Cialis, 4773, Generic viagra, ifvmzo, Viagra generique, ryjjmo,


Generic cialis online

February 17th, 2014 at 10:34 pm


Faxless payday loans

March 3rd, 2014 at 1:46 pm

, Online casino games, maee, Essay, hdcltu, Silagra, 5109, Cialis, %-]], Faxless payday loans, 967, Order viagra, qsyknm, Payday loans, %]], Cash advance loans, 392, Online dating, qbwira,


Buy generic cialis

March 13th, 2014 at 10:24 pm


Disposable electronic cigarette

May 5th, 2014 at 11:40 pm

lskaolopxmfehfgspnjogpsnbujpo, Electronic cigarettes complaints, lADxgKY, [url=http://decorativehardwaredirect.com/]Electronic cigarette starter[/url], nvHKbsy, http://decorativehardwaredirect.com/ Janty electronic cigarette, SmholmB.



June 24th, 2014 at 4:58 am

Vicodin & Alcohol Pregnant Osteoporosis Of The Feet Bone Density . Diabetes Related To Obesity National Heart Lung And Blood Institute Cipro And Side Effects Buy Orlistat Dubai Osteoporosis Diagnosis Canada Fluoxetine For Bulimia Cognitive Behavioral Therapy Apcalis Sildenafil Citrate No Prescription Online Viagra Generic Australia . Topamax Interactions Migraine Headaches Mexico Prescriptions Fluconazole Prednisone Weight Lifting Stretch Marks Keflex 300 Mg. Instantly Raise Your Blood Pressure Taking Ranitidine When Pregnant Specialty Skin Care Lincolnshire Hair Loss Ladies Birth Control Pills .
Amiodarone Cheapest Website. Buy Amiodarone Paypal.
Buy Lisinopril No Rx Needed - Cheap Lisinopril Uk
Online Pharmacy Calutide Cheap, Calutide Online Cod
No Prescription Glimepiride Next Day - Buy Glimepiride Online With Mastercard
Buy Metaxalone Free Consultation, Buy Metaxalone Pills
How To Buy Seizures Online Without A Prescription, Order Seizures From Canada
Buproban Visa Overnight -> Buproban Next Day
Overnight Shipping For Slimfast, Slimfast With Next Day Delivery Without Prescription With Free Shipping
Adefovir Generic FedEx NO PRESCRIPTION, Buy Adefovir With Echeck
Cheap Zantac Canada Order Zantac With NO PRESCRIPTION



July 31st, 2014 at 9:09 pm

What’s up Jackson, if you are a new internet user then you have to visit daily this web site and read the updated content at at this place. cddkkbdcfegd

Comment Form

About this blog

Where is the knowledge we have lost in information?
- T.S. Elliot, The Rock

We are drowning in data - exabytes of it. My research explores technologies that can help us organize, structure, and efficiently search huge amounts of information as well as automatically deduce actionable pieces of knowledge from it. Learn more

I was a PhD student at the University of Maryland with research interests in databases, artificial intelligence, and machine learning. Learn more

My Homepage: http://www.matthiasb.com
Also on Twitter: @MBroecheler

  • www.youtube.com: Hello There. I discovered your blog the usage of msn. This is a very smartly written article. I wil [...]
  • Iqxqcdin64: XRztslqkcx2014 Kristen has taken on the role of a soldier who is assigned to Guantanamo Bay in the f [...]
  • best foam mattresses 2014: Link exchange is nothing else but it is just placing the other person's blog link on your page at su [...]
  • Johng258: What's up Jackson, if you are a new internet user then you have to visit daily this web site and rea [...]
  • Yqachohj93: Cheap Oakley Sunglasses [...]