4 ms·

I have a requirement of checking group membership wherein a group may contain > 10K members. Each member is an 8byte ID. Do you think Xor filter would be a bett

by devj 6y ago

I have a requirement of checking group membership wherein a group may contain > 10K members. Each member is an 8byte ID. Do you think Xor filter would be a better fit compared to Bloom here? Or am I looking at it the wrong way? Thanks.

gopalv 6y ago
> Do you think Xor filter would be a better fit compared to Bloom here? The 8byte key is the only scenario where you should consider XorPlus (i.e a 8 bytes mapped to a long). The lookup properties of the Xor filter are better with that case, but the real question is whether you have an entire collection to start building the bitset or not. The sketch production isn't incremental - there is no add(k) after building it once. So you can't build add data once it is built, while the Bloom filters do support adding entries after the fact (in fact, it can add bloom filters into it, rather than sending all the new keys). And both of those approaches are missing an unset operation.
- devj 6y ago
  Sorry.. Forgot to mention that. Yes insertion/deletion is required and the frequency may be higher. The exact usecase is that group membership is dependent on some conditions. We schedule this check every 15 minutes and based on it, we are adding/deleting the members.
  - cakoose 6y ago
    Xor filters require all the members of the set be provided up front. Bloom filters allow adding members, but not removing them. Cuckoo filters allow removing members: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf And just for completeness, storing everything losslessly in a btree, radix tree, or hash table would probably be under 300 kB. (80 kB just for the IDs plus, say, an additional ~2x overhead.)
    - throwaway_pdp09 6y ago
      Safe removal is only possible if you know it is already in filter. The 'you can delete from cuckoo filters' bit I feel is often oversold.
      - cakoose 6y ago
        Oh wow, I only read the paper's abstract and was fooled. Thanks for the correction.
  - antman 6y ago
    You can use a counting Bloom Filter that allows deleting. Depending on your update requirements you might also be ok with two bloom filters, one for that has the group memberships and one that has group removals.
  - im3w1l 6y ago
    10k members every 15 minutes? Just rebuild it from scratch.
    - rbanffy 6y ago
      Or use a Cuckoo fiter.
- the8472 6y ago
  > The sketch production isn't incremental - there is no add(k) after building it once. Which means they can't be used for distributed set intersections, unions or cardinality estimations, a not insignificant side-benefit of bloom filters.
contravariant 6y ago
Might as well use a simple hashmap if that's all you have. Unless you have some extreme performance requirements.
- anfilt 6y ago
  This has much better storage/memory bounds than a hash table. The end result is less cache misses.
  - throwaway_pdp09 6y ago
    A hash map is better than a hash table? I don't understand, genuine question, aren't they the same thing or am I getting confused about what you're saying?
    - iainmerrick 6y ago
      Hash map and hash table are the same thing here. That’s what the GP suggests using. (And it’s the right suggestion.) Bloom filters, cuckoo filters and XOR filters are all types of probabilistic lookup, which are different from normal hash tables.
  - contravariant 6y ago
    Sure, but 10K items is so little that you might as well not bother. If you're worried about memory usage you can also just scan the whole table each time (no such thing as a cache miss when the whole table fits in cache).
    - anfilt 6y ago
      This is better than a hash table for membership testing. As for compared to table scan depends on your key size and number of keys. This algorithm means you could easily have more than 10k especially for larger keys, and still likely reside in one of the cache levels. Heck a lot CPUs cant hold 10k items in L1. Like for 64 bit numbers thats 80Kb. Let alone for something like UUIDs or other larger sparse keys. Also main memory access is aprox. delay of a few thousand cycles. Iterating a table of 10,000 items is going to be close to that. A hit in L1 is about 3 cycles. So a table scan is possibly slower or close to equal since a super scalar cpu has multiple execution ports. Soon as you start getting any larger its easily gonna be slower to do a table scan. This also gives you O(1) queries and being smaller means that table is more likely to reside in cache for any given look up. This smaller memory footprint is a great boon for any hash algorithm that involves look up.
throwaway_pdp09 6y ago
Is performance an issue? If not, occam says go with the simplest which is bloom. If performance matters and you are prepared to burn a bit more mem for speed, blocked bloom filters, which are likely optimal for speed and still simple.
dirtydroog 6y ago
Are the ids sparsely distributed?
unwind 6y ago
How does plain binary search perform? 80 KB is not a lot to cache, if you do many lookups misses should go down, right?
Uptrenda 6y ago
Do you mean like 10,000 valid members or 10,000 candidates (where the set might only contain a small number of valid members?)
iainmerrick 6y ago
That’s a very small dataset. Just use a normal HashSet / dict / whatever is normal in the language you’re using.
asah 6y ago
Try hyperloglog (HLL) which is another terrific and widely-available algorithm for set membership. All these algorithms are statistical, and should be checked by hand in the second phase, e.g. not-member is reliable but is-member should be confirmed.

by devj 6y ago

gopalv 6y ago

> Do you think Xor filter would be a better fit compared to Bloom here? The 8byte key is the only scenario where you should consider XorPlus (i.e a 8 bytes mapped to a long). The lookup properties of the Xor filter are better with that case, but the real question is whether you have an entire collection to start building the bitset or not. The sketch production isn't incremental - there is no add(k) after building it once. So you can't build add data once it is built, while the Bloom filters do support adding entries after the fact (in fact, it can add bloom filters into it, rather than sending all the new keys). And both of those approaches are missing an unset operation.

devj 6y ago
Sorry.. Forgot to mention that. Yes insertion/deletion is required and the frequency may be higher. The exact usecase is that group membership is dependent on some conditions. We schedule this check every 15 minutes and based on it, we are adding/deleting the members.
- cakoose 6y ago
  Xor filters require all the members of the set be provided up front. Bloom filters allow adding members, but not removing them. Cuckoo filters allow removing members: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf And just for completeness, storing everything losslessly in a btree, radix tree, or hash table would probably be under 300 kB. (80 kB just for the IDs plus, say, an additional ~2x overhead.)
  - throwaway_pdp09 6y ago
    Safe removal is only possible if you know it is already in filter. The 'you can delete from cuckoo filters' bit I feel is often oversold.
    - cakoose 6y ago
      Oh wow, I only read the paper's abstract and was fooled. Thanks for the correction.
- antman 6y ago
  You can use a counting Bloom Filter that allows deleting. Depending on your update requirements you might also be ok with two bloom filters, one for that has the group memberships and one that has group removals.
- im3w1l 6y ago
  10k members every 15 minutes? Just rebuild it from scratch.
  - rbanffy 6y ago
    Or use a Cuckoo fiter.
the8472 6y ago
> The sketch production isn't incremental - there is no add(k) after building it once. Which means they can't be used for distributed set intersections, unions or cardinality estimations, a not insignificant side-benefit of bloom filters.

contravariant 6y ago

Might as well use a simple hashmap if that's all you have. Unless you have some extreme performance requirements.

anfilt 6y ago
This has much better storage/memory bounds than a hash table. The end result is less cache misses.
- throwaway_pdp09 6y ago
  A hash map is better than a hash table? I don't understand, genuine question, aren't they the same thing or am I getting confused about what you're saying?
  - iainmerrick 6y ago
    Hash map and hash table are the same thing here. That’s what the GP suggests using. (And it’s the right suggestion.) Bloom filters, cuckoo filters and XOR filters are all types of probabilistic lookup, which are different from normal hash tables.
- contravariant 6y ago
  Sure, but 10K items is so little that you might as well not bother. If you're worried about memory usage you can also just scan the whole table each time (no such thing as a cache miss when the whole table fits in cache).
  - anfilt 6y ago
    This is better than a hash table for membership testing. As for compared to table scan depends on your key size and number of keys. This algorithm means you could easily have more than 10k especially for larger keys, and still likely reside in one of the cache levels. Heck a lot CPUs cant hold 10k items in L1. Like for 64 bit numbers thats 80Kb. Let alone for something like UUIDs or other larger sparse keys. Also main memory access is aprox. delay of a few thousand cycles. Iterating a table of 10,000 items is going to be close to that. A hit in L1 is about 3 cycles. So a table scan is possibly slower or close to equal since a super scalar cpu has multiple execution ports. Soon as you start getting any larger its easily gonna be slower to do a table scan. This also gives you O(1) queries and being smaller means that table is more likely to reside in cache for any given look up. This smaller memory footprint is a great boon for any hash algorithm that involves look up.

throwaway_pdp09 6y ago

Is performance an issue? If not, occam says go with the simplest which is bloom. If performance matters and you are prepared to burn a bit more mem for speed, blocked bloom filters, which are likely optimal for speed and still simple.

dirtydroog 6y ago

Are the ids sparsely distributed?

unwind 6y ago

How does plain binary search perform? 80 KB is not a lot to cache, if you do many lookups misses should go down, right?

Uptrenda 6y ago

Do you mean like 10,000 valid members or 10,000 candidates (where the set might only contain a small number of valid members?)

iainmerrick 6y ago

That’s a very small dataset. Just use a normal HashSet / dict / whatever is normal in the language you’re using.

asah 6y ago

Try hyperloglog (HLL) which is another terrific and widely-available algorithm for set membership. All these algorithms are statistical, and should be checked by hand in the second phase, e.g. not-member is reliable but is-member should be confirmed.