4 ms·
If you want a simple explanation of bloom filters: To add to filter: 1) Get multiple hashes of the data. You can use the same hash function and increment the
by Assossa 9y ago
If you want a simple explanation of bloom filters:
To add to filter:
1) Get multiple hashes of the data. You can use the same hash function and increment the data each hash, or use multiple hash functions. You can do any amount of hashes from 1 to infinity, each filter size and dataset size has a sweet spot.
2) Mod (remainder) each hash by the filter size. The filter size can be any size, 1 to the maximum hash from your function[s]. The larger the filter, the more accurate the results, but a filter larger than your dataset is obviously useless.
3) Set each bit at the locations (from step 2) in the filter to 1.
To check filter:
1) Do steps 1 & 2 from previous procedure.
2) Check each location in the filter. If all locations are 1, the data might be in the filter. If any of the locations are 0, the data is definitely not in the filter.
- taco_emoji 9y ago> a filter larger than your dataset is obviously useless This isn't obvious to me, can you explain?
- biggerfisch 9y agoAt that point, it's harder to search/test than just looking at your dataset, so there's no point to making the size that large
- irl_zebra 9y agoWell,the bloom filter only uses a tiny bit of space per data element and doesn't actually store the data. When searching the data itself, you're often searching through the actual data, which is more intensive and slow.