 |
|
| FriendFeed is the easiest way to share online. Learn more » |
Joel Franusic › Likes
A practical scalable distributed B-tree - http://www.hpl.hp.com/techrep...
Nagender Parimi, binic, Dmitry 'radiant' Volkov and 76 other people liked this
"Moreover, our algorithm is conceptually simple: we use transactions to manipulate B-tree nodes so that clients need not use complicated concurrency and locking protocols used in prior work. To execute these transactions quickly, we rely on three techniques: (1) We use optimistic concurrency control, so that B-tree nodes are not locked during transaction execution, only during commit. This well-known technique works well because B-trees have little contention on update. (2) We replicate inner nodes at clients. These replicas are lazy, and hence lightweight, and they are very helpful to re- duce client-server communication while traversing the B-tree. (3) We replicate version numbers of inner nodes across servers, so that clients can validate their transactions efficiently, without creating bottlenecks at the root node and other upper levels in the tree."
- Paul Buchheit
Paul, I think many of us are going to trust your opinion on this white paper. All Greek to me.
- Jon-Paul Bussoli
All I understand is that it is in my best interests to cheer for the way you access B-tree nodes in order to continue to enjoy friendfeed reliably. Go friendfeed algorithm go!
- Jon-Paul Bussoli
What, no comparison to BigTable?
- ⓞnor
@nor It's really not the same thing, unless somehow you're using a distributed B-tree on hash collision, however, if you're getting that many collisions, then the hash algorithm is probably wrong or your key width is too small. Then again, I really don't know what I'm talking about.
- Eric Florenzano
Curious as to what problem Paul is looking at... My default data toolkit these days would probably include sqlite for in-memory data, sharded bdb's for btrees that are too big for memory, and hbase/hypertable for a distributed store. I wonder where this fits in...
- DeWitt Clinton
Ok this is a really *nerdy* post! :*)
- Susan Beebe
DeWitt, I just thought that it looked like an interesting paper. As for the several solutions you mention, I don't know that any of them have distributed transactions (maybe bdb, but that doesn't really work).
- Paul Buchheit
B-Trees and Prof. Bayer http://wwwbayer.informatik.tu-... - would be interesting to know what he'd say, unfortunately he's retired a few years ago. Used to be fairly approachable in all matters B-Tree.
- Mustafa K. Isik
@DeWitt - no room for a traditional SQL based database except as an in memory database?
- Nick Lothian
we had designed and implemented distributed tree control, but transactions were considered "too much" for near-real-time, and they were already in protocol... the rest you know as xGSN boxes in GPRS/3G/HSDPA - dynamic routing for mobile packet networks. I'd left team in 2003...
- A.T.
@paul - I'll readily admit to being out of my depth, but it depends on what the definition of "distribution transaction" is. With bdb a combination of local transactions and guaranteed consistent replication you can approximate a distributed transaction at the cost of speed. See http://www.oracle.com/technol... and http://www.oracle.com/technol.... But those won't work across bdb shards.
- DeWitt Clinton
@paul - A table-based distributed store can do this via a lock on entity groups, where entity groups are defined by relationship formed by instances of similar models that belong to the same parent-based ancestry chain. This is how App Engine transactions work -- see http://code.google.com/appengi... and http://code.google.com/appengi.... Ping ryan for some background there. Not sure if hbase or hypertable support this via their api.
- DeWitt Clinton
@nlothian - I dunno. Offline maybe?
- DeWitt Clinton
DeWitt: have you ever successfully used BDB with millions of newly written entries and transaction support turned on? We kept getting transaction logs with millions of entries that were never consumed, so restarts would take hours as it replayed the logs. Configuring BDB to work for large databases is insanely esoteric to say the least, and it may be impossible to get it to work acceptably in some cases.
- Bret Taylor
@bret -- no, definitely not with large databases. We used bdb's heavily at my last company, though. Aggressive sharding is the key if you want to support either transactions or replication, which matches intuition about how it is implemented.
- DeWitt Clinton
But your comment about millions of entries makes me wonder about which data is getting written to which place. I suspect a lot of problems like this end up with the bulk of the data being written transactionless + replicated to a table-based store (or a transactionless bdb), and only a small subset of the data gets transaction support. So multiple datastores. But you guys know this better than I do, so why am I rambling? : )
- DeWitt Clinton
DeWitt, you can also look into all the trouble that Gaia had with bdb - I simply wouldn't trust any fancy bdb functionality.
- Paul Buchheit
Also, AppEngine transactions are limited to a single "entity group", which I assume means a single BigTable tablet. Essentially, they solved distributed transactions by not having them -- all transactions must be local to a single tablet. From the docs: "Every entity belongs to an entity group, a set of one or more entities that can be manipulated in a single transaction. Entity group relationships tell App Engine to store several entities in the same part of the distributed network."
- Paul Buchheit
@paul - yup, that's the trade-off. Entity groups ensure locality, locality makes transactions fast(er). Same old lever problem -- speed of consistency vs. scope of the transactions.
- DeWitt Clinton
DeWitt, there's nothing wrong with having local transactions -- I'm just pointing out that they aren't distributed transactions.
- Paul Buchheit
Point taken. I got way off-topic regarding your original post anyway.
- DeWitt Clinton
The design seems reasonable. The only part that is under-specified is the way they switch from a master node to a slave. I'm curious why they don't use transactions to maintain replicas but instead rely on some unspecified master/slave replication scheme.
- Private Sanjeev
Budgeting: Living Wage Calculator Tabulates American Cost of Living - http://lifehacker.com/5086343...
Joel Franusic liked this
Do Not Post Pictures of This Sign to the Internet. Seen off of I-101N. [PIC] - http://www.reddit.com/r...
![Do Not Post Pictures of This Sign to the Internet. Seen off of I-101N. [PIC]](http://thumbs.reddit.com/t3_79zvn.png "Do Not Post Pictures of This Sign to the Internet. Seen off of I-101N. [PIC]") |
Joel Franusic, Atul Arora, Aaron Krug and 14 other people liked this
Any ideas on what the code is?
- Paul Buchheit
they look like they could be software activation keys, which would explain why youre not supposed to post them on the internet too :P
- bob
Reverse psychology?
- Gabe
may be it's some kind of study and the code is the identification number for the sign :p
- Avi Mehta
Where's Sandra Bullock when you need her!?
- AJ Kohn
986F 64B9 3005 E03E. FC42 A41E BD57 3179
- AJ Batac
Well done AJ, good thinking!
- Rich
Terrorist 'tweets'? US Army warns of Twitter dangers - http://news.yahoo.com/s...
Joel Franusic, Mirco, Jens Christian Freund and 10 other people liked this
I read somewhere that terrorists use eating utensils and toilet paper as well. Is nothing sacred anymore?
- Jay Cuthrell
qthrul wins the internets for the evening!
- FFing Enigma (aka Tina)
Eyeroll.
- Rochelle
here's a better link for information on the study - http://blog.wired.com/defense...
- Jeff Quinton
I also understand that terrorist use porn sites and embed messages in JPEG headers
- Robert Hafer
I defy anyone to blow something up in less than 140 characters. I'm calling bullshit.
- Oldengrey (Jay)
OMFG. What if they use IM?!?! The terrorists might be able to like talk in like real-time and shit. And like not see the FAIL whale.
- ld
All the CIA/FBI/DHS needs to do is keep an eye on Favrd and wait for the terrorists to start favoriting each other’s tweets.
- Guillermo Esteves
This is ridiculous...
- Susan Beebe
British security ministry is asking for back doors to Skype because terrorists and other criminals are using Skype encrypted calls.
- Phil Wolff
from twhirl
qthrul, that was brilliant.
- Alejandro
the study (if you see the Wired link I posted) is a threat assessment of possibilities, it's not some urgent warning - it was an academic paper of what-ifs.
- Jeff Quinton
thanks everyone... I'm here all week. please try the fish.
- Jay Cuthrell
I think they should worry less about Twitter and more about sites like icanhascheezburger and the posibilities of steganography. Those might not really be lolcats.
- April Russo (app103)
Coming soon ... Twitter encrypted 2.0
- Charlie Anzman
No more software patents? (too good to be true?) - http://www.patentlyo.com/patent...
Jeroen De Miranda, siavash, John Lam and 72 other people liked this
"The Patent and Trademark Office has now made clear that its newly developed position on patentable subject matter will invalidate many and perhaps most software patents, including pioneering patent claims to such innovators as Google, Inc. In a series of cases including In re Nuijten, In re Comiskey and In re Bilski, the Patent and Trademark Office has argued in favor of imposing new restrictions on the scope of patentable subject matter set forth by Congress in § 101 of the Patent Act. In the most recent of these three—the currently pending en banc Bilski appeal—the Office takes the position that process inventions generally are unpatentable unless they “result in a physical transformation of an article” or are “tied to a particular machine.”[1] Perhaps, the agency has conceded, some “new, unforeseen technology” might warrant an “exception” to this formalistic test, but in the agency’s view, no such technology has yet emerged so there is no reason currently to use a more inclusive standard."
- Paul Buchheit
from Bookmarklet
The author of this blog clearly thinks that getting rid of software patents would be bad and would somehow hurt Google. However, I believe that the existence of software patents is a much greater risk for Google (and other innovators) than benefit. Google is about a lot more than Pagerank (and competitors already have comparable if not the identical algorithms). Meanwhile, the thousands of patents that they don't own effectively form a giant minefield that could hurt them at any moment (see RIM).
- Paul Buchheit
(grabs papers, runs to patent office)
- Karim
Like = trying to figure out the issue. Some software probably should be patentable, but the standards are too murky to sort out. Probably the PTO wants to wash its hands of the mess.
- Sean McBride
Looks like it's time to go the 'trade secret' route instead of the 'patent' route. It's kind of nice: If it's something that's obvious from the user experience it should be harder to patent, but if it's something that, even when the service is public, can still be hidden, then third parties shouldn't just be able to copy it. One-click shopping shouldn't be protected, but O(1) search algorithms should be. (Wait, what? If there were an O(1) search algorithm it'd change everything! I contradict myself.)
- Kevin Fox
I like the "physical transformation" argument. Computer technology has boomed in spite of software patents, not because of them.
- Gabe
I admire the ironically pro-competition and social progress roots of patents. I also respect the efforts of many to equitably apply those antiquated laws on the violently innovative realm of software and the Internet. Nevertheless, I will be so happy to see the USPTO concede the futility of these patents and pull the plug. (Though, depending on what kind of plug and how they pull it, they may owe someone royalties.)
- Christopher Sacca
Patents are a tax on small bazaar innovation in favor of big cathedral innovation. In some fields maybe that makes sense. But despite all the patents I've filed for, the things that had the biggest impact on the world weren't patentable (and shouldn't have been). Patents fetishize the "inventor" and the "invention" at the cost of actual progress.
- Daniel Dulitz
I wonder if this will put those of us who work on "physical transformations" even further behind. Did you know it currently takes and average of about 15 months from the time an order is placed for a wind turbine (example large equipment) until it is operational? This is part of the argument for patents... you can eventually recoup the cost of this large equipment if it works enough better than your competitors during the protected period.
- Clare Dibble
I still can't believe that Yahoo/Flickr tried to patent "interestingness" of social media. Does anyone know how I can find out the status of this patent request from 2006? http://appft1.uspto.gov/netacgi... The patent office's search sucks and I can't find it anywhere there.
- Thomas Hawk
With equipment/ material costs rising, will this just make software even more attractive relative to say consumer goods or energy?
- Clare Dibble
Many large corporations do not file their really key technologies. They just lock them up. This makes it impossible for market competitors to find out what they are up to.
- Paul Denlinger
Chris, with respect to chord progressions, I think you are thinking of "copyright" and not "patent" ;-)
- Karim
I am so happy to hear this. I want Blackboard to go out of business. O
- Akshay Dodeja
was discussing this with a friend and he posited an interesting question: will this make it even more important to keep the employees who work on developing new technologies happy?
- Marco(aureliusmaximus)
See also http://arstechnica.com/article... regarding the studies of innovation & patents in IT vs BioTech fields, and possible reasons
- Nick Lothian
I also think the EFF is a great resource for this stuff. Their Patent Busting project is fantastic. http://w2.eff.org/patent/ I was on the wrong end of one of those Acacia patents once and it made me sick to my stomach.
- Christopher Sacca
I think this is great news, especially for big companies like Google, Microsoft, Apple, etc. Larger companies have more to lose from potshot lawsuits than to gain. Very little of software business success comes from having a patent on a process - it's all about execution, and legal defense prevents those who are producing working software from doing what they do best.
- Jon Galloway
Oh please let this mean that the one-click patent can be consigned to the garbage can of history. We demand easier shopping!
- Earle Martin
So who would a decision like this be bad for? Besides patent trolls, and maybe patent lawyers...
- nadim
i never end up reading the original article that these long response feeds are based on...so even here, the original writer gets no credit for stimulating this conversation. So who's to say people should own anything. The Fugees sampled Enya for "Ready Or Not" and gave her no credit, but I am sure Enya got the idea from somewhere. Again this is cyclical, or tangential rather. But where is the place for barter in this world then? I think the human instinct to barter is always going to trump giving stuff away
- Rajesh
A follow-up from GrokLaw: "It's one lawyer's opinion and analysis, one with a stake in the outcome. Would you like to see what another lawyer says about the subject, in contrast?" http://www.groklaw.net/article...
- Simon
I fear that today's Amazon outage will bring back the armchair architects -- that was always the most annoying part about the Twitter outages.
Gus Perez, Dave Dash, Chu Yeow and 32 other people liked this
If really want to understand these kinds of problems, start here: http://en.wikipedia.org/wiki...
- Paul Buchheit
We're discussing this on today's Elite Tech News podcast. http://www.talkshoe.com/talksho...
- Louis Gray
You're about an hour or so too late: http://friendfeed.com/e...
- Mark Trapp
Paul it seems that EC /AMI API kinda triggered the S3 outage.. while trying to resolve on thing, they may have taken something else down on the S3 EU /US farms.. not sure.. but like you say Murphys law always prevails :)-
- Peter Dawson
Yeah, I saw that Mark. In the future, I will demand 7000 nines from all my service providers :)
- Paul Buchheit
7,000? That's amateur hour. I require at least 8,000 before i sign a vendor contract.
- Mark Trapp
Amazon can crash as much as they want and still be more reliable than almost anyone else creating their own system. It's the internet. Shit breaks. Especially on Sunday mornings.
- Nicholas Molnar
The Amazon outage hurt Vator for several hours. Ouch
- Bambi Francisco
Reliability is overrated. People say they want it but it's not that high up on the list. Look at cell phones vs ultrareliable land lines. And people use Twitter, Windows, etc. Their actions suggest they don't care as much about reliability as they say they care.
- Amit Patel
I agree with Amit. For years and years, Windows crashed over and over again, and yet people kept buying the next version.
- Piaw Na
@Amit, in the world of cell phones, could we equate coverage and reliability? Not just geographic reach, but indoor penetration. It is the number one reason given from customers who change providers. The data show Sprint and T-mobile have 2x the churn rate of AT&T and VRZN, with most of that delta attributable to coverage differences. That said, overall the churn rates are in the low single digit percentages, so even if coverage/reliability is the high on customers' list, most don't do anything about it.
- Christopher Sacca
Any everything has to go to Windows bashing. Interesting. My Mac crashed today. I guess I don't care about that either, running Parallels.
- Stephan Miller
from Alert Thingy
@Sacca: I think coverage and reliability go into the list of things people complain about but most don't care enough about to actually switch products. People get very emotional when something goes wrong, and swear they'll act, and then they quickly forget. Actions speak louder than words. (Tangent: “gas boycott”) @Stephan: My mac crashes far more than Windows, and I keep using it. :)
- Amit Patel
do all of the 7000 nines have to be consecutive?
- banksean
Reliability is overrated. I buy that.
- Claudio Cicali ♋
well, for web services - yes, reliability is overrated... general opinion seems to be that web service ARE toys, and you don't expect your kid toys to be *reliable*, do you? :)
- A.T.
@sacca churn rate is low only because American wireless operators play on the edge of anti-trust law (or that law is not tight enough) and chain their customers with few year contracts. Make it as it is done in Europe - and you will see true churn rate, or better say "run on bank" if operator makes even one serious mistake.
- A.T.
@amitp when you say "people", would you please to add "some"? because some of us just _DO_ first and then open mouth - only you don't know that. In other words "people" != "some people"...
- A.T.
Star Wars Photoshop Content by Worth 1000 - http://feeds.laughingsquid.com/~r...
Joel Franusic, Visiting Europe, beth rhinelander and 4 other people liked this
California High Speed Rail Authority Interactive Map - http://www.cahighspeedrail.ca.gov/map...
Steve C, Emily Miller, Joel Franusic and 6 other people liked this
They've been talking about doing this forever, right? Do you think it'll get built anytime soon?
- Dan Hsiao
from Bookmarklet
We can only hope... and vote in November...
- Ross Miller
Dude! 2030?!?!?!?!?
- Jini
@Jini: 2020. The system should be in service in 2020, and become "commercially self-sustainable" in 2030, when it would cross 100M passengers/year. From the text of proposition 1 (which you should vote for in November): "At a minimum, the entire 700-mile system described in the High-Speed Rail Authority’s Business Plan should be constructed and in revenue service by 2020." See http://www.leginfo.ca.gov/pub...
- Tudor Bosman
Construction should start in 2010, and 10 years to build a California-wide train system is a long time, but not unreasonable. Of course, judging by how long it took for BART service to be extended to the San Francisco airport after the project was approved, I'd say 2050 is a more realistic opening date...
- Tudor Bosman
I'd pay extra to not have to go through Fresno.
- Jim Norris
Sonoma County votes "Yes", Marin County votes "No". Marin is delaying me from accessing SF via smart public transport. Get your "Yes" vote on, Marin!
- Andrew Meyer
i just really like the site! great visualization at work here.
- michael sean wright
Nothing good ever starts from Fresno.
- Steve C
Find Who Has Access to Your Gmail Account - http://googlesystem.blogspot.com/2008...
Kirb, Carl, Nikpay and 16 other people liked this
Double Like. I'm very glad so see that this has been implemented. I wonder if it will show the FBI and NSA sessions though ;)
- Paul Buchheit
yes, those show up as coming from 127.0.0.1 :-D
- Karim
looks like a good security feature :) not showing up for me yet, but should be a nice & reassuring
- immaterial
Had a nightmare that someone was cyber-stalking me through my lifestream! They hacked twitter or something and framed me.
Joel Franusic liked this
California construction codes liberated -- now free for download - http://www.boingboing.net/2008...
Joel Franusic liked this
Fooled by Randomness: The Hidden Role of Chance in Life and in the Markets - http://www.amazon.com/dp...
 |
RAPatton, Stuart Woodward, Joel Franusic and 9 other people liked this
Cover is great.
- Urbansheep
I read that several years ago and it really moved me, both by Taleb's personal stories and by his "black swan" idea.
- Fred Yankowski
I'm Joining Craigslist in July - http://feeds.zawodny.com/~r...
Gavin, Diana Valerini, Chris Garrett and 113 other people liked this
All the best with the transition and new gig.
- Paul Jacobson
from twhirl
Congrats!
- Ginger Makela Riker
Seriously one of the most awesome things I've read all day. Welcome to the neighborhood, Jeremy!
- DeWitt Clinton
Congrats!
- Ha3rvey (not Akiva)
Congratulations!
- Atul Arora
Jeremy, that's AWESOME. Congratulations. Looking forward to seeing you more in SF!!!
- David Sifry
from twhirl
I didn't see anybody predict that! Great news. Should be interesting.
- Louis Gray
good luck!
- Chris Harris
Congrats.
- Russellreno
all the best!
- Ron Emrick
Congrats! :) some people were expecting you here on FF...
- directeur
Congrats! That seems like a great company to be a part of.
- Jeremy Brooks
Jeremy I'm right there with you!
- Randy Carranza
Congrats, real good choice that I am sure you will enjoy
- Fred Grott
@Louis yeah, I was tempted to mess with people and post pics of myself at FriendFeed and various other places, but decided to come clean. [Note: I still think FriendFeed would be an awesome gig too...]
- Jeremy Zawodny
Congratulations!
- Ernest Prabhakar
Nice move Jeremy
- Dennis Howlett
from twhirl
wow...that's great. congratulations!!!
- don loeb
Congrats, Jeremy
- Bret Taylor
Congratulations! Is this a long-term thing or just a casual encounter?
- Jim Norris
JZ4CL
- Kevin Fox
congrats! good luck with that commute!
- Jeremy Toeman
awesome. Great move.
- Keith Teare
Congrats and good luck!
- John Frost
seems like that would be a great place to be. congratulations.
- edythe
Cool! Congrats!
- C. K. Sample III
from twhirl
very kool....best of luck to ya.
- (jeff)isageek
Congrats!
- Jeremiah Owyang
that is so friggin AWESOME. damn!
- dave mcclure
Barack Obama - Computer Science Question - http://www.youtube.com/watch...
  |
Michael C. Harris, Sam Harmon, Ivan Campos and 38 other people liked this
he doesnt really answer though, just says you shouldnt use the worst kind of sort :P
- bob
Would that be the McCain sort or the Bush sort?
- Kevin D. White
he's all about balance
- Phil Smirnov
32-bit images?
- TranceMist
Bubble sort is far from the worst Robby :)
- Paul Buchheit
Is the deterministic bogosort better or worse than the random bogosort? I think the deterministic flavor is harder to write correctly, but the random one is susceptible to bad interactions with PRNG's.
- ⓞnor
haha, for instance a version which counts to a billion between each step of the sort? are there any commonly known/discussed ones which are worse?
- bob
haha
- bob
Who phone-screened this guy?
- Neil Kandalgaonkar
I agree with bob's take on worse sorts: the only thing worse i can think of is 10,000-monkey sort: randomly shuffle the elements in the array, and check every once in a while to see if they're sorted. It always bothers me that we even discuss bubble sort.
- j1m
J1im, within an infinite amount of parallel universes there will always be an infinite amount of universes where monkey sort works the first go... which seems to make it somewhat unreliable but also extremely fast!
- Philipp Lenssen
Yes, "monkey sort" = "random sort" = "bogosort" (see the wikipedia link). It has great best-case performance, and people joke about the O(N) "quantum bogosort" (mentioned in the article). That best-case performance is unfortunately nearly optimal, though it's surely a good idea to do the shuffle first, because a pre-sorted array is probably a common case.
- ⓞnor
Even though I'm not a US citizen (aware of the global impact of US presidential elections), he definitely bought me after watching this video.
- Nenad Nikolic
Bill O'Reilly Freaks Out Off Camera - http://www.youtube.com/watch...
 |
Joel Franusic, Ray Grieselhuber, Franz Kratochvil and 33 other people liked this
Ahahahahahah...*inhale*...hahahahahaha.... :-)
- cmiper
Muhahaha :D
- Marius Quadflieg
Where did *THAT* come from? (and: what is it?)
- Alex von Halem
Removed due to copyright. Oh well.
- Bwana ☠
Removed due to insanity, more like. Glad I was on FF and got to see it b4 it was removed. Actually: I'm not sure I should be so glad. Some things are better kept under the rug.
- Alex von Halem
That was great
- Lee Stranahan
from Alert Thingy
Another copy here... http://www.youtube.com/watch...
- cmiper
They are taking them down as soon as a new copy goes up. Try here, maybe NSFW ads. http://www.collegehumor.com/video:1...
- cmiper
love it!
- sixbit
Ok, that was pretty funny. Pure frustration.
- Bwana ☠
Gawker has re-posted the video http://gawker.com/5008668...
- Scott Beale
That was great. (thanks for the link Scott)
- Alejandro
Also see: http://www.npr.org/yourtur...
- Atul Arora
Is this hosted somewhere else?
- Steve Lynch
It's on the College Humor site still... http://www.collegehumor.com/video:1...
- cmiper
Goes to show: you can't remove something from the internet. If you act like a douche in front of a camera, you're going to have to live with it. Thanks for the laughs, Bill.
- ben bloch
Really. What a douche.
- Alex von Halem
here is an active link http://view.break.com/501946
- Dobromir Hadzhiev
When Specialty Plates Go Hilariously Wrong - http://jalopnik.com/388728...
 |
Misha, Ambar Pansari, Kevin Gough and 48 other people liked this
Dang. Just one! I wanted more.
- Louis Gray
You wanted another specialty plate, or another kid to eat? ;)
- Ana
What, Louis? One more delicious kid?
- Akiva Moskovitz
How can you have any pudding if you don't eat yer kids?
- Morton Fox
I'd feel left out if I didn't join the bandwagon on this one. I've never seen so many "Likes". Man I wish I'd been able to get my phone camera to work the morning I saw the plate that unintentionally said 490BEY. Andre the Giant would approve.
- Kamilah Gill
Cuckoo hashing - Wikipedia, the free encyclopedia - http://en.wikipedia.org/wiki...
 |
Dmitry 'radiant' Volkov, A.T., Jeff Quinton and 30 other people liked this
"When a new key is inserted, a greedy approach is used: The new key is inserted in one of its two possible locations, "kicking out", that is, displacing any key that might already reside in this location. This displaced key is then inserted in its alternative location, again kicking out any key that might reside there, until a vacant position is found, or the procedure enters an infinite loop. In the latter case, the hash table is rebuilt using new hash functions. Lookup requires just inspection of two locations in the hash table, which takes constant time in the worst case."
- Paul Buchheit
linked list
- atalmatal
Ah, those wacky hashing algorithms. I used to study these.
- Morton Fox
this is giving me a headache... need more Malbec wine!
- Susan Beebe
@Paul From what you pasted it sounded like as if they'd be using some sort of linear probing, but the "alternative location" is apparently computed by re-hashing, utilizing another hash function. Interesting that despite occasional table rebuilds, performance proves to be good in some very standard cases.
- Mustafa K. Isik
"The basic version of cuckoo hashing has load factor limited to 49%." -- that's pretty much overhead. I'd say if it's possible to design a good hash function (that is, you know what you are storing), the basic hash table with open addressing will behave as well, while having 2 times less memory overhead.
- Igor Sereda
makes me feel so dumb and inadequate !!
- viki saigal
Igor: There are hashing schemes with less memory overhead, but the nice thing about cuckoo hashing is the constant lookup time, which is not guaranteed with most other hash tables.
- Bernhard Bauer
49% doesn't sound great, but "Generalizations of cuckoo hashing that use more than 2 alternative hash functions can be expected to utilize a larger part of the capacity of the hash table efficiently while sacrificing some lookup and insertion speed. Using just three hash functions increases the load to 91%."
- Paul Buchheit
An example of better algorithms: takes more time at start-up (in this case, building the hash table) in order to get better performance at run-time. See http://www.stoweboyd.com/message....
- Stowe Boyd
Bernhard: I see, that makes is well-suited for realtime tasks, that is, if you don't need realtime insertions.
- Igor Sereda
In terms of speed (not predictability), much depends on how keys are compared and how hashes are calculated. For example, if you have int keys, a lookup into open addressing hash table with "+1" index increment on collision will be very fast thanks to memory caching -- I bet it will be faster in most collision cases than cookoo hashing, despite larger number of compares.
- Igor Sereda
TechCrunch update: My life feels better when I don't read every single TechCrunch headline... Unsubscribing was definitely the right choice!
Joel Franusic liked this
It's all about moderation. Miss you Grant!
- Frances Haugen
Ooo, handy trick for sleeping your Mac's display (not the whole computer): http://www.leopardtricks.com/leopard... #tips #macosx
Joel Franusic liked this
Other ways to read this feed:
