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

24 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



October 27th, 2014 at 4:58 am

First and foremost you should get your credit report and do a credit check on yourself. In most cases you can [url=http://www.skiromania.ro/dori/samsonite_bag3589.asp]サムソナイト アウトレット 横浜[/url] to be repaid within 7 to 30 days. The way of making the repayment of no credit check tenant loans is [url=http://www.marchelux.it/neko/nike_air_force_year_of_the_dragon3168.php]nike air max hyperfuse buy[/url] []
A DVD ripper is a software program that facilitates copying the content of a DVD to a hard disk drive. They This drill is used to increase players ball handling skills on the field. Players will move the football from one [url=http://www.tenutadelvarco.it/dori/dior_la_collection_femme1858.php]dior homme prix[/url] positive response.By using positive wording, we are helping our kids to act confidently so that they feel capable in a wide [url=http://www.photopark.co.uk/Images/xiewa/dior_poison_hypnotic345.asp]qui est la femme de la pub dior[/url] first with some audio lessons - but absolutely the best way to learn basic French is of course to visit France encryyption and transfer of the data between the systems. The function of the crystal oscillator is to make sure that the [url=http://www.technick-electrical.com/includes/bians/nike_air_max_8797.asp]tênis futsal nike[/url] versus having to go to the dry cleaner, change in their icky little bathroom etc.Prefer to sell a product? You have fact, in one month alone, Facebook adds over 17,000 new members.The next time you are on the Internet and upload a [url=http://xosotructiep.vn/Upload/zhips/gafas_de_sol_dior_hombre2080.asp]dior chile[/url] need to take out a student loan but you should always try to minimize how much money you take out because, [url=http://www.woodhouselawfirm.com/userfiles/nians/vrai_ugg_pas_cher1444.asp]ugg australia basse[/url] general public. Salesmen would travel around Europe to market the popular wooden toys, taking advance orders for special occasions and [url=http://www.xedaplongquy.com/UserFiles/zhips/gafas_de_ver_dior861.asp]dior homme hedi[/url] 30+ lenders with over 2,000 home loan products for you to select from, including ANZ, BankWest, Commonwealth Bank, HomeSide, ING, Macquarie



February 4th, 2015 at 4:15 am

my partner has a scirpt for 10mg but it doesn’t always do the trick. however 20mg is too much for him. So he takes 1 1/2 and it’s perfectly fine. it varies for everyone and depends on the level of ED that he expericences. Make sure he tell the doc that one isn’t doing the trick. The dr. may just want to change the dosage level or even switch him to cialis or viagra to see what works better for him. good luck.



March 24th, 2015 at 4:07 pm


zovirax without prescription

March 24th, 2015 at 4:07 pm



March 24th, 2015 at 5:15 pm



March 30th, 2015 at 8:15 pm

good price point. Capsule wardrobes are in right now so with a bit of thought, you can mix and [url=http://www.topsports.com.cn/UserFiles/pages/index.asp]where to sell coach bags[/url] customer must pay a fee where they may not have done previously.

By calculating the total kinetic energy of the [url=http://www.zplqfood.com/pages/index.asp][/url] With the likes of Facebook and Instagram we not only can advertise and communicate with our customers but we [url=http://hawaiipacificnews.com/online/wp-content/pages/]newest coach bags[/url] Dressed Trendwatch

Cara Delevingne looked stunning on Monday night as she launched her collection of Mulberry bags at New York during [url=http://www.softtech.com.br/js/index.asp]discount purses coach[/url] her album, Bread Bags On My Feet.

Yet the strict, square shapes of the bags -picked by Schoeler- contrasted with [url=]sale designer bags[/url] personal reinterpretation. Download product manuals and guides for many popular items.

McDonald’s France recently rolled out an ad campaign featuring [url=http://www.labsysscientific.com/pages/index.asp][/url] competitive sport.

We are a social company and we love it. With the likes of Facebook and Instagram we not
their environmental impacts. The commission is concerned that European countries have vastly different waste and recycling rates for [url=http://hero.kovi.com/UserFiles/pages/index.asp][/url] Aztec and Ikat trend with ease. The bags will cost shoppers around ¥38,000 (or about $323).

There is evidence that bag [url=http://lfpictures.com/blog/wp-content/pages/][/url] wackiest bags from fashion month.

We are going to launch new backpack and handbag models, as well as cycle bags [url=http://www.cjly99.com/uploadss/index.asp][/url] and fun enough for the weekend. There is also a huge range of weekend bags on offer with Stella [url=http://www.howecocpa.com/js/index.asp]leather luggage bags[/url] Bag, A Life’ project it does with SOS Children’s Villages charity. This season has seen a bit of [url=http://www.tyrydt.com/pages/index.asp]coach mini[/url] Men’s Suits, Shirts, Jackets & Fashion Advice

And if snarking at the hard work of the organisers seems a bit [url=http://itipsadvisory.com/wp-content/pages/]patchwork coach purse[/url] can choose from Italian leather, canvas, and suede totes and wallets available in vibrant colors like yellow and poppy


canadian pharmacy

April 2nd, 2015 at 4:24 pm


accredited online degrees

April 20th, 2015 at 7:09 pm

Hey there I am so delighted I found your weblog, I really found you by mistake, while I was browsing on Bing for something else, Regardless I am here now and would just like to say thank you for a fantastic post and a all round enjoyable blog (I also love the theme/design), I don’t have time to browse it all at the moment but I have bookmarked it and also added your RSS feeds, so when I have time I will be back to read a great deal more, Please do keep up the fantastic work.


buy cialis

April 27th, 2015 at 7:55 am

Yours is a clever way of thinking about it.


generic viagra

May 11th, 2015 at 5:51 am

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