3 ms·
Show HN: Morton Filter: Fast, Self-Resizing Alternative to Bloom Filter
- runFun 8y agoA cuckoo filter is a Bloom filter replacement that supports deletions and which often uses less memory. This code base implements a Morton filter, a revamped cuckoo filter that is, respectively, up to 15.5x, 1.3x, and 2.5x faster for insertions, deletions, and lookups than the original implementation out of CMU. It uses a compressed block format that enables in-situ reads and updates on a logically sparse, yet compactly stored filter (i.e, without block materialization). It particularly excels when the filter is bigger than L3 cache. Morton filters also support self-resizing like a quotient filter but resize up to 20x faster. The research paper appeared at the 2018 VLDB Conference. A subsequent extended version has been invited to appear in the VLDB Journal.
- ben509 8y agoThe paper[1] has a nice explanation of both Morton filters and the prior Cuckoo filters. I've read a bit about cuckoo hashing, and this seems like a natural extension of the idea. [1]: https://www.vldb.org/pvldb/vol11/p1041-breslow.pdf https://www.vldb.org/pvldb/vol11/p1041-breslow.pdf