You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Currently the user is responsible to ensure that there are no duplicated keys. We should handle this for the user (it is relatively easy to do efficiently, without even sorting).
Hi! I've been trying to understand the implications of duplicated keys.. apologies if this is a naive question, but does this situation not just imply the key was already previously added to the set, and thus 'there is no work to be done' in order to add that key to the set for future testing of "is-key-in-set"?
@slimsag You construct a filter from a set of keys. It is assumed in the construction that the keys are distinct. If two keys are the same, then the construction will always fail because the algorithm won't manage to add both of them.
So it would be really nice to handle duplicate keys for the user, since we are computing the 64-bit hash digest for each key. But I don't fully understand how to do this without using sort algorithm. Would be helpful if I can get some reference on that ..
I totally agree that we need to fix this. I just never got around to doing it.
(So I am not dismissing your concerns, at all.)
But I don't fully understand how to do this without using sort algorithm. Would be helpful if I can get some reference on that ..
If the construction succeeds, then you know that there were no duplicated keys. So there is no need to do any work.
If the construction fails, and only then, do you need to handle the duplicate keys. There should be no need to sort because the failed construction should have left you with unmatched keys... and that number should be small... And, e.g., if x and y are equal then both x and y should be unmatched at the end.
You can try it out by simulating a case where you have two identifical keys... you will see what happens after the first failure...
I have tried to measure the performance improvements for the following APIs.
populate() - accepts an array of keys, for each key compute the hash digest,
and insert the digest into BTreeMap for deduplication.
populate_keys() - accepts an array of u64 digests, and insert each digest into
BTreeMap for deduplication.
build_keys() - accepts an array of u64 digests, that are expected to be unique
so there is no overhead of computing the hash and inserting the hash into
BTreeMap. This can be considered as the reference performance of Fuse8 filter.
We now support a small number of duplicates. If there are too many duplicates, the user will get a reported failure but this should not happen if the hash values are fair and good.
Activity
thomasmueller commentedon Dec 20, 2019
Yes it would be nice. What algorithm would you use? I'm afraid I'm not aware of a very efficient one...
lemire commentedon Dec 20, 2019
Try to construct the filter once (optimistically). The duplicated keys will be in the unmatched keys, just visit these keys.
emidoots commentedon Feb 1, 2021
Hi! I've been trying to understand the implications of duplicated keys.. apologies if this is a naive question, but does this situation not just imply the key was already previously added to the set, and thus 'there is no work to be done' in order to add that key to the set for future testing of "is-key-in-set"?
lemire commentedon Feb 1, 2021
@slimsag You construct a filter from a set of keys. It is assumed in the construction that the keys are distinct. If two keys are the same, then the construction will always fail because the algorithm won't manage to add both of them.
prataprc commentedon Aug 27, 2021
In the rust implementation of Xor8 and Fuse8 I am adding the following API.
So it would be really nice to handle duplicate keys for the user, since we are computing the 64-bit hash digest for each key. But I don't fully understand how to do this without using sort algorithm. Would be helpful if I can get some reference on that ..
lemire commentedon Aug 27, 2021
@prataprc
I totally agree that we need to fix this. I just never got around to doing it.
(So I am not dismissing your concerns, at all.)
If the construction succeeds, then you know that there were no duplicated keys. So there is no need to do any work.
If the construction fails, and only then, do you need to handle the duplicate keys. There should be no need to sort because the failed construction should have left you with unmatched keys... and that number should be small... And, e.g., if x and y are equal then both x and y should be unmatched at the end.
You can try it out by simulating a case where you have two identifical keys... you will see what happens after the first failure...
lemire commentedon Aug 27, 2021
@prataprc If I am not providing details is because I don't know how to do it because I never spent time on it. I am just reasoning from a high level.
lemire commentedon Sep 6, 2021
I have a fix in the Go version at FastFilter/xorfilter#22
I'll port it here, but @prataprc would you be so kind to check whether it meets your need?
prataprc commentedon Sep 6, 2021
Ported this patch to rust-fuse8
I have tried to measure the performance improvements for the following APIs.
populate()- accepts an array of keys, for each key compute the hash digest,and insert the digest into BTreeMap for deduplication.
populate_keys()- accepts an array of u64 digests, and insert each digest intoBTreeMap for deduplication.
build_keys()- accepts an array of u64 digests, that are expected to be uniqueso there is no overhead of computing the hash and inserting the hash into
BTreeMap. This can be considered as the reference performance of Fuse8 filter.
Before the patch,
After the patch
These numbers were for building 10 Million keys, and the machine used was
1st gen thread-ripper.
lemire commentedon Sep 6, 2021
So I take it that you are happy with this solution. :-)
lemire commentedon Sep 7, 2021
We now support a small number of duplicates. If there are too many duplicates, the user will get a reported failure but this should not happen if the hash values are fair and good.
lemire commentedon Sep 7, 2021
Closing for now.