4
$\begingroup$

Because if it is the case, this really suits my need.

I'm trying to discover popular searches on a website. For this, I'm using TopK algorithm which is based on Bloom Filter hashing.

I don't want "Hello world" and "hello world" to be count twice. So if it is a collision, that would be really appropriate for my use case.

Practically, I'm using this implementation.

Practically, I can run String similarity prior to adding to TopK bucket, like for any new string item, if it is similar to at least one String in the bucket, then convert it to the one in the bucket before adding. But this would be stacking same logics (in case it could be achieved directly with Bloom filters).

$\endgroup$

1 Answer 1

4
$\begingroup$

It depends on the hash function but in general no, because standard hash functions are designed to avoid that similar objects have similar hash codes. [edited, see comment]

For your use case you should probably use a custom hash function which makes it more likely for two strings to have the same code. A one-hot encoding of the characters or characters bigrams in the string might work.

$\endgroup$
4
  • $\begingroup$ very nice, so running a prior String similarity before adding to bucket is a good option you think ? instead of messing with Hash function itself (seems a headache, but I will try) $\endgroup$
    – bacloud14
    Commented Dec 12, 2021 at 13:06
  • $\begingroup$ I think I'm repeating myself, let's try customising the hash function. $\endgroup$
    – bacloud14
    Commented Dec 12, 2021 at 13:18
  • 1
    $\begingroup$ Minor nitpick: for the letters A–Z, the difference between their uppercase and lowercase versions (in ASCII or Unicode) is exactly one bit. $\endgroup$ Commented Dec 12, 2021 at 23:13
  • $\begingroup$ @IlmariKaronen I didn't know, interesting. $\endgroup$
    – Erwan
    Commented Dec 13, 2021 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.