Replying to Avatar jb55

researching a way to build a minimal perfect hashmap of words to store alongside the binary note in nostrdb so that nostrdb clients (damus ios, damus notedeck, zaptream rust) can do O(1) mute word matching, which is pretty important for performance when you have 100s of mute words.
Avatar
ynniv 1y ago

Sounds like a Bloom filter in front of a radix trie

Reply to this note

Please Login to reply.

Discussion

Avatar
jb55 1y ago

BBHash does say its bloom-filter based. hmm!

https://github.com/rizkg/BBHash

Avatar
ynniv 1y ago

I think this is just a bloom filter. With only a few target words and a lot of potential ones, even with a multihash scheme you'll end up with a lot of false positives. For those you'll also need some way to reliably rule them out, and a radix tree is one implementation.