xorfilter

> Rather than determining if the current site has been submitted by querying the Firebase/Algolia APIs with every page you visit, the extension contains regularly-updating Bloom filters for all submitted HN stories to preserve user privacy. Nice! I built a pi-hole esque stub dns-resolver that uses Bloom Filters generated from hostfiles (60 MiB, 5M entries --> 2 MiB with 1% false positives) and it worked like a charm. At some point, I also looked into Xor Filters which are apparently even lighter and faster but couldn't find a JavaScript implementation for it [0]. I; however, stopped using Bloom Filters because its immutability meant building it over and over again which was a pain. Inverted Bloom Filters [1] or Spectral Bloom Filters [2] might have been useful since they can be updated in-place. Instead, I went for storing hostnames in a

"Membership test: returns true if the key x is likely in S, false otherwise" I think they circumvent the problem by making a complicated insertion procedure where all of the keys need to be inserted at once, it seems uses a stack to avoid hash collisions Take a look at https://github.com/FastFilter/xorfilter/blob/master/xorfilte... I can usually read go, but I've never been that great at deciphering "academic code" so the exact details escape me here.