News for hackers. Stuff that matters.

A comment on Xor Filters: Faster and Smaller Than Bloom Filters.

Re:Xor Filters: Faster and Smaller Than Bloom Filters by layoutIfNeeded on Thursday December 19, 2019 @11:51PM (#21841784)
Interesting. Where does 3 come from for the number of hash functions? Why not 4 or 5?
[ Parent | on HN ]
Re:Xor Filters: Faster and Smaller Than Bloom Filters by fixf on Friday December 20, 2019 @01:29AM (#21842101)
The minimum number motivated to work is also the cheapest. 2 was simply deemed insecure.
[ Parent | on HN ]
Re:Xor Filters: Faster and Smaller Than Bloom Filters by thomasmg on Friday December 20, 2019 @02:37AM (#21842316)
No, actually 2 would also work. It's just that 3 hash functions needs the least space for some reason (less than 2, less than 4 or more).
[ Parent | on HN ]
Re:Xor Filters: Faster and Smaller Than Bloom Filters by fixf on Friday December 20, 2019 @04:04AM (#21842660)
Well met, and thanks for identifying the solution using overhead.
[ Parent | on HN ]
Re:Xor Filters: Faster and Smaller Than Bloom Filters by layoutIfNeeded on Friday December 20, 2019 @02:48AM (#21842366)
Insecure? What does that mean in the context of a read-only data structure?
[ Parent | on HN ]
Re:Xor Filters: Faster and Smaller Than Bloom Filters by fixf on Friday December 20, 2019 @03:34AM (#21842542)
Good point, loose language on my part. I am thinking of false positives or collision. The required statistical properties aren't met.
[ Parent | on HN ]