Neutral mention · rule
the reference in the repo is paywalled (US$ 30!). I did find this https://arxiv.org/pdf/1912.08258 which may or may not be related. but what I found interesting is that the construction looks alot like perfect hashes
Back to the collection
Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters
Thomas Mueller Graf, Daniel Lemire
2019 · arXiv
- HN score
- 0
- Mentions
- 6
- Readers
- 6
- Months
- 5
From the abstract
The Bloom filter provides fast approximate set membership while using little memory. Engineers often use these filters to avoid slow operations such as disk or network accesses. As an alternative, a cuckoo filter may need less space than a Bloom filter and it is faster. Chazelle et al. proposed a generalization of the Bloom filter called the Bloomier filter. Dietzfelbinger and Pagh described a variation on the Bloomier filter that can be used effectively for approximate membership queries. It has never been tested empirically, to our knowledge. We review an efficient implementation of their approach, which we call the xor filter. We find that xor filters can be faster than Bloom and cuckoo filters while using less memory. We further show that a more compact version of xor filters (xor+) can use even less space than highly compact alternatives (e.g., Golomb-compressed sequences) while providing speeds competitive with Bloom filters.
Metadata: arXiv. Abstracts retain their original authors’ rights.
In the conversation
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
6 selected excerpts · 6 total mentions
Neutral mention · rule
> check the literature for various alternatives that are better in specific situations For direct replacements, see Xor(+)-Filters: https://arxiv.org/abs/1912.08258 and the subsequent evolution into Binary Fuse Filters: https://arxiv.org/abs/2201.01174
Neutral mention · rule
This paper seems to use an un-optimized Bloom filter implementation. It also lists cuckoo filters to be 10 times faster than Bloom filters. In other papers, e.g. the cuckoo filter paper and the xor filter paper, the difference is _much_ smaller; maybe factor 2. https://dl.acm.org/doi/pdf/10.1145/2674005.2674994 - figures 5 and 6 https://arxiv.org/abs/1912.08258 - figures 3b and 4b
Neutral mention · rule
Or you go with Xor filters, which are more efficient than both Cockoo and Bloom filters. [0] [0] https://arxiv.org/abs/1912.08258 ("Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters")
Neutral mention · rule
He probably did not talk about it because this post was an announcement of his paper: https://arxiv.org/abs/1912.08258, the XOR filter description starts at page 3.
Neutral mention · rule
Direct link to paper (pdf) - https://arxiv.org/pdf/1912.08258.pdf I haven't fully read the paper yet, but it seems like a variation of a bloom filter where membership is determined by xoring three hashes (see algorithm 1 in the pdf)
Keep following the thread.
More in Machine learningMore from the same topics.
2020arXiv
Language Models are Few-Shot Learners
Tom B. Brown, Benjamin Mann, Nick Ryder +28
Recent work has demonstrated substantial gains on many NLP tasks and benchmarks by pre-training on a large corpus of text followed by fine-tuning on a specific task.
83 mentions35 months
3HN score
2016arXiv
Understanding deep learning requires rethinking generalization
Chiyuan Zhang, Samy Bengio, Moritz Hardt +2
Despite their massive size, successful deep artificial neural networks can exhibit a remarkably small difference between training and test performance.
16 mentions14 months
2.5HN score
2016arXiv
End to End Learning for Self-Driving Cars
Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski +10
We trained a convolutional neural network (CNN) to map raw pixels from a single front-facing camera directly to steering commands.
8 mentions7 months
2.5HN score
2018arXiv
Categorizing Variants of Goodhart's Law
David Manheim, Scott Garrabrant
There are several distinct failure modes for overoptimization of systems on the basis of metrics.
8 mentions7 months
2.5HN score