News for hackers. Stuff that matters.
Re:Opposite of a Bloom Filter by ComputerGuru on Friday January 25, 2013 @07:16AM (#5115077)
Guys, this is real. http://www.somethingsimilar.com/2012/05/21/the-opposite-of-a...

Yes, it's a hash table without conflict resolution. No, that's not the joke.

From the article:

The simplest data structure that fits the description of a “opposite of a Bloom filter” is a hash map. With a large corpus like the one we were dealing with, the memory consumed by a hash map is far too large and its growth is bound only by corpus size. However, from this simple idea a more fruitful one comes out.

The design I pitched uses an array, a hash function, and the ability to swap ids in and out of the array concurrently. The hash function and the array are used in the same way they are inside of a hash map implementation. Unlike a typical hash map implementation, the array size is bounded and hash collisions are not avoided.

Re:Opposite of a Bloom Filter by martinced on Friday January 25, 2013 @09:22AM (#5115489)
As I understand it there's more to it than simply being a hashmap without collision resolution: performance.

They mentioned hundreds of thousands of events per second. At that level typical Java objects and locks simply do not cut it anymore. That is why, for example, LMAX wrote their disruptor pattern using gigantic primitives array and fast CAS, no locking, operations.

So here they're using a very fast "hashmap" updated by using CAS operation which do not lock.

Why would it be a joke that said!? There are use cases for Bloom Filters, so there probably are for what they created here too no!?

Re:Opposite of a Bloom Filter by andrelaszlo on Friday January 25, 2013 @05:41AM (#5114871)
Isn't this just an implementation of the filter described by Wilt and Wither back in 2003?
Re:Opposite of a Bloom Filter by pretoriusB on Friday January 25, 2013 @06:37AM (#5114972)
I'm amused by the above comment, and all the wild assumptions it makes.

Whereas a Bloom filter is relatively well known (in compsci circles), how many people know:

1) Who Wilt and Wither are? 2) What they "described back in 2003"?

Are they scientists? Did they wrote a paper in 2003 describing something similar? Have them or anybody else implemented anything based on their description?

The use of the word "just" especially, is, err, especially misguided.

Can you point to other implementations? If not then it's not "just an implementation", it's the FIRST FRIGGING IMPLEMENTATION!

Re:Opposite of a Bloom Filter by othermaciej on Friday January 25, 2013 @06:45AM (#5114995)
I think it's a joke - "Wilt" and "Wither" both being opposites of "Bloom".
Re:Opposite of a Bloom Filter by pretoriusB on Saturday January 26, 2013 @11:02AM (#5120673)
Sorry, but I'm not a native english speaker, so the joke went over my head.

(And while I now recognise "wither" I didn't knew at all about the "wilt" word)

Re:Opposite of a Bloom Filter by othermaciej on Monday January 28, 2013 @09:36PM (#5132045)
It was an overly subtle joke, took me a while to get it myself.
Re:Opposite of a Bloom Filter by andrelaszlo on Friday January 25, 2013 @08:28AM (#5115251)
Sorry, my sense of humor doesn't work well before I have coffee. If ever.
Re:Opposite of a Bloom Filter by pretoriusB on Friday January 25, 2013 @06:39AM (#5114981)
Damn it gets even more amusing!

A Google search for "Wilt Wither 2003" doesn't return anything relevant (at least in the first 2-3 pages).

Re:Opposite of a Bloom Filter by dexen on Friday January 25, 2013 @08:16AM (#5115215)
Discussed before: (meta: how's that for reverse bloom filtering? ;-)

http://news.ycombinator.com/item?id=4251536 http://news.ycombinator.com/item?id=4251759

tl;dr:

> Specifically, it functions the same as a cache with a random removal policy, (...)

> you might as well have an LRU valueless cache if locality is going to play a role.

Re:Opposite of a Bloom Filter by seanmcdirmid on Friday January 25, 2013 @05:38AM (#5114865)
It took me awhile to get the joke. Its simply a unique mapping dictionary with a fixed number of buckets and no hash key conflict resolution.
Re:Opposite of a Bloom Filter by gojomo on Friday January 25, 2013 @05:33AM (#5114855)
Previously posted and discussed:

http://news.ycombinator.com/item?id=4251313

Re:Opposite of a Bloom Filter by CJefferson on Friday January 25, 2013 @08:17AM (#5115217)
Out of interest, is there any difference between this, and a cache?

It is still nice to see a bloom filter as the opposite of a cache of course. In effect a cache contains a subset of the things it has seen, and a bloom filter keeps a superset.

I have used something like this to great effect when doing calculations which do many complex trigonometric calculations, which often end up using a small set of input values. Something similar can be used before any expensive pure function call, where you expect to see the same values called repeatedly, but don't want to use unbounded space, or have to write a complicated cache management system.

Re:Opposite of a Bloom Filter by jergosh on Friday January 25, 2013 @10:34AM (#5115849)
A Moolb filter?
Re:Opposite of a Bloom Filter by htp on Friday January 25, 2013 @01:18PM (#5116799)
I was thinking "Gloom filter", what with the possibility of reporting false negatives.
Re:Opposite of a Bloom Filter by martinced on Friday January 25, 2013 @09:25AM (#5115503)
I responded to a first comment but then read the others...

I think you guys are all missing the point: they're talking about crazy high perfomances.

They've implemented it using non-locking algorithms, like LMAX's disruptor pattern (gigantic primitives arrays, CAS operation).

It's not a "joke" to be able to process 12 millions events per second on a single core in Java (that's where the LMAX disruptor patter is at right now, and it shall go higher once Oracle fixes the JVM so that it uses a faster CAS operation when possible [it's possible on many mainstream CPU and there are RFEs for this]).

The point here is that it is fast. As in "faster than anyone commenting here that is a joke could have ever build".

Re:Opposite of a Bloom Filter by seanmcdirmid on Friday January 25, 2013 @09:55AM (#5115646)
Why should I take what we all learn in computer architecture 101 seriously? Ya, it's crazy fast, but someone in the 50s or 60s invented it, and we should all know this class of algorithms like the back of our hands.

Bloom filters are interesting because they reverse what we typically do, the reverse again is then not that interesting. So I thought this was a joke.

Re:Opposite of a Bloom Filter by pi18n on Friday January 25, 2013 @09:59AM (#5115672)
I hope this won't come off as tactless, but is there something going on in there more significant than CAS and writing to the database if it's a different value? Because I do non-blocking programming as a hobby and I'd love to know.