3 ms·
Seems like a good place for a bloom filter. If the overwhelming majority of words seen don't match, you would win by rejecting non-matches quickly. If instead
by moloch-hai 4y ago
Seems like a good place for a bloom filter.
If the overwhelming majority of words seen don't match, you would win by rejecting non-matches quickly. If instead it almost always matches, you will need to look at all the bytes anyway to be certain of a match.
- Dylan1312 4y agoBloom filters are a fantastic datastructure but more applicable when the search set is large (usually greater than can fit in-memory). If using a bloom filter with a small set, it's possible to obtain a low probability of false positives by using just one hash function and a small number of buckets. At that point you've effectively got a hashset like one of the solutions described in the blog post.
- moloch-hai 4y agoThe idea was that you maintain a running hash as bytes arrive, and drop out on the first that doesn't match. A separate hash table for what gets past would check for false positives, using the final hash value.