hur.st

> Check out this excellent visualization by Thomas Hurst showing how parameters influence each other: > https://hur.st/bloomfilter/ Blush. However will I cope with all this extra traffic? One common way to improve bloom filter cache performance is to divide them into blocks - elsewhere is mentioned doing it to the cache line, but it would be interesting to see how much performance would be gained with a more naive approach, for instance, splitting the filter into 4KiB pages. I've done this for disk-backed filters, but never looked to see if it improved performance generally.

Vernor Vinge's A Fire Upon the Deep (1992) depicts a galaxy of countless highly advanced civilizations in the far future - and describes its "net" as "the net of a million lies". However, it also depicts every message with an AI's best judgement of its reliability - for example: >From: Sandor Arbitration Intelligence at the Zoo [A known military corporation of the High Beyond. If this is a masquerade, somebody is living dangerously.] More examples here: https://hur.st/afutd.html (spoilers if you read more than the From lines)

There are 555,278,657 passwords in the database. With a Bloom Filter, you could quickly rule out potential inputs. Even better, there is no need to hash the input, because... it's already a cryptographic hash. The input SHA-1 provides 160 bits of hash. If we divide that up into 5 hash values of 32 bits, we can get a 3% false positive rate with a 483 MiB Bloom Filter (which will easily fit in memory). https://hur.st/bloomfilter/?n=555M&p=0.03&m=&k= This will be blindingly fast. We're talking 5 random reads from memory. Even in the worst case of 5 cache misses, we're still well under 1us. This will let us return "not found" for 97% of inputs that aren't in the database. If we get a hit there, then we could turn to a larger bloom filter for greater accuracy, but we'd have to actually hash the key to get more hash bits. Of course if you get hits for all your bloom filters, you still have to do a real lookup to positively confirm that the key is in the database.

The limit given in the article is 360KB (on floppy). At that size, you can't use Tries, you need lossy compression. A Bloom filter can get you 1 in 359 false positives with the size of word list given https://hur.st/bloomfilter/?n=234936&p=&m=360KB&k= The error rate goes up to 1 in 66 for 256KB (in memory only);

https://hur.st/bloomfilter/ There is a only bloom filter calculator that lets you just mess arpund with parameters

Where did you get the number 2MB? According to this calculator, a bloom filter for 16M elements with a 10% false positive rate would be 9MB. https://hur.st/bloomfilter/?n=16m&p=10&m=&k=

1024 capacity, 1 in 1M false positive rate. (false positives fail safe- sending something the client already has), 3.6KB https://hur.st/bloomfilter/?n=1024&p=1.0E-6&m=&k=

“This looks really promising! A Bloom Filter that represents a set of million items with a false-positive rate of 0.01 requires only 9585059 bits and 7 hash functions.“ My immediate thought here was that this wasn't very space efficient as it requires over 9 bits per item? I'd have to dig more into this though to confirm or deny my intuition! Edit: this page agrees with the blog post and shows some interesting graphs https://hur.st/bloomfilter/?n=1000000&p=0.01&m=&k=

> I think what I am trying to say is that cooking can never be standardized, nor should it. Not that this is what is being attempted here, but rather than one or more recipes that each represents a particular set of curated choices, you could instead create a "recipe as multidimensional model" that captures the entirety of the configuration-space for "the food that is called X", where you can both adjust inputs and see how output parameters (e.g. saltiness, acidity, viscosity) will change, or constrain output parameters to find optimal input parameters. In other words, something like https://hur.st/bloomfilter/, but for tuning your chocolate-chip cookies.

I'm not sure if 1/1000 is the right tradeoff. You can get 1/100000 for less than double the size. https://hur.st/bloomfilter/?n=500M&p=100000&m=&k=

~391 MB if we store SHA-1 hashes of the URLs (160 bits each) and HN ids and assume 16.3 million posts[1]. (Probably less, since, as you said, some posts are just comments.) If we're okay submitting one out of every hundred URLs as a SHA-1 hashed value to an external server, we can reduce that further to ~18 MB with a bloom filter[2]. [1]: https://www.google.com/search?q=(160+bits+%2B+32+bits)+*+16.3+million&… [2]: https://hur.st/bloomfilter?n=16300000&p=0.01

Here's a helpful calculator, it will even tell you the optimal number of hash functions. All you have to know is the expected cardinality of the set. https://hur.st/bloomfilter

That's probably because it's a tiny filter. In reality you'd calculate the size more appropriately: http://hur.st/bloomfilter?n=4&p=1.0E-20 Here you can give it a false positive rate you're happy with and a number of elements. It'll give you the optimal size and number of hashes to use. Your suggestion would use far too much space.

Background A bloom filter is a bitmap which lets you test if an item is a member of a set, in constant time and constant space. It tells you with 100% certainty if the item is NOT in the set, and it tells you with variable certainty if the item MIGHT be in the set. In other words, it answers yes/no if an item is in the set, but there's a chance of false positives, but no chance of false negatives. The probability of a false positive is based on the number of items in the set, and the number of bits in the bitmap. Here (http://hur.st/bloomfilter) is a calculator, for example, which lets you say how many items are in the set, and what probability you want for false positives, and it tells you how many bits should be in the bitmap, and how many bits you should set each time you are adding an element into the filter (they call this 'number of hashes'). So you can imagine there are a lot of really interesting applications for bloom filters when you want a really fast, compact way of knowing if something is LIKELY to be true. Like, 'is this request in my cache?' Bloom filters can also be used to provide some interesting privacy-preserving properties. In Bitcoin, for example, you have a wallet with money stored at a bunch of addresses, and unused addresses where new money can come in. You don't want anyone to just be able to look into your wallet and know all your addresses, but you DO want to be notified when someone sends you money. So you load up a bloom filter with a bunch…