Re:One Hash Bloom Filters
by FreakLegion on Monday October 19, 2026 @08:03PM
(#50159640)
NB: You're trading non-negligible space efficiency here, which gets worse as you lower the false positive rate. Partitioning means uneven occupancy rates across partitions, and either you accept low occupancy (increased filter size overall) or you're pretty much guaranteed to have hot blocks (increased false positive rate for specific partitions).
Re:One Hash Bloom Filters
by senderista on Monday October 19, 2026 @10:27PM
(#50160642)
You are describing "blocked" bloom filters here (i.e., the k hash functions are evaluated in a single block which is initially chosen by the hash). "Partitioned" bloom filters (i.e., each hash function is evaluated in a separate partition) don't have the imbalance problem you describe.
Re:One Hash Bloom Filters
by FreakLegion on Monday October 19, 2026 @11:11PM
(#50160912)
I'm describing the data structure from the article, which is partitioned twice: first into 64-byte, then into pairwise coprime-sized chunks. The 64-byte chunks are what you're quoting as "blocked", the pairwise coprime-sized chunks as "partitioned". The space inefficiency I mentioned applies to the 64-byte chunks.
Re:One Hash Bloom Filters
by FreakLegion on Thursday October 22, 2026 @01:46AM
(#50191624)
More cache misses, and also an increased false positive rate from doing multiple lookups. A similarly optimized cuckoo filter (cache line-sized buckets/windows and SIMD queries) is both smaller and faster.
Re:One Hash Bloom Filters
by aidenn0 on Tuesday October 20, 2026 @02:11AM
(#50161977)
Given that they are partitioning into cache-line sized blocks, I assume they are partitioning as a time-space tradeoff?
[edit]
Rereading that section more carefully, they are concerned about concurrent write performance to the bloom filter; since two CPUs can not write to the same cache-line in parallel, it's definitely done for performance reasons.
Re:One Hash Bloom Filters
by FreakLegion on Tuesday October 20, 2026 @06:17AM
(#50163872)
It's absolutely a speed optimization, although more for reads than writes. The 64-byte cache line bit is a standard blocked Bloom filter. Add SIMD queries and that's about as fast as these things get.
The other side of the tradeoff is bumped ribbon retrieval. Blocked Bloom filters are about 50% bigger than BuRR.
Re:One Hash Bloom Filters
by gwittel on Monday October 19, 2026 @07:38PM
(#50159456)
I hadn’t seen that one hash paper before. This is a really cool optimization over Miztenmacher. Do you have benchmark numbers with different input sizes you can share?
I’ll have to read the paper and code more, but it seems like this would be amenable to supporting filter merges as well (as long as the new size doesn’t exceed the filters’ capacity).
Re:One Hash Bloom Filters
by AlotOfReading on Monday October 19, 2026 @11:07PM
(#50160896)
The one hashing scheme should be technically better.
That said, I suspect you could avoid the coprime partitions and the issues they cause with semi-correlated permutations over block partitions and avoid hash collisions in the process.
Re:One Hash Bloom Filters
by senderista on Monday October 19, 2026 @10:20PM
(#50160587)
Something like this? 64-bit hash, 9 bits to address all the bits in a 64-byte cache line, so 7 hash functions addressing the bits in a cache line can be extracted from a 64-bit hash?
Re:One Hash Bloom Filters
by rickcarlino on Tuesday October 20, 2026 @08:57AM
(#50165666)
Gnutella and Gnutella2 used something like a single hash bloom filter to route p2p file queries across the mesh in a less wasteful manner. It was not perfect, but it worked enough to scale to very large user counts.
https://lph.ece.utexas.edu/users/krimer/pub/im11_bf.pdf
[edit]
Rereading that section more carefully, they are concerned about concurrent write performance to the bloom filter; since two CPUs can not write to the same cache-line in parallel, it's definitely done for performance reasons.
The other side of the tradeoff is bumped ribbon retrieval. Blocked Bloom filters are about 50% bigger than BuRR.
I’ll have to read the paper and code more, but it seems like this would be amenable to supporting filter merges as well (as long as the new size doesn’t exceed the filters’ capacity).
(source - I wrote MurmurHash/SMHasher and have used the above in my own bloom filters and cuckoo hash tables)
That said, I suspect you could avoid the coprime partitions and the issues they cause with semi-correlated permutations over block partitions and avoid hash collisions in the process.
Depends how big the bloom filter is. Most hashes are big and their bits are independent.
https://rickcarlino.com/notes/p2p/how-gnutella-scaled-to-han...