Replying to Avatar ᴛʜᴇ ᴅᴇᴀᴛʜ ᴏꜰ ᴍʟᴇᴋᴜ

bloom filters of the event IDs and the user IDs will help a lot for fast elimination of non-matches

maybe some kind of "current list" event with the account fingerprints - i dunno how good npub entropy is but probably the first 12 bytes zero chance of collisions within one user's follow list, probably 8 bytes is enough - to make actually finding the nprofiles easier
Avatar
the axiom 2y ago

Is a bloom filter faster than a hashset or a linked list in this case?

Reply to this note

Please Login to reply.

Discussion

Avatar
ᴛʜᴇ ᴅᴇᴀᴛʜ ᴏꜰ ᴍʟᴇᴋᴜ 2y ago

since the data is mutable probably a cuckoo filter is better

the benefit of using the filter is that when a relay is watching streams of events come in and a user has a subscription open this can eliminate a lot of work checking the list of follows

the filters sometimes false positive but they never false negative, so if the cuckoo filter says no then you can skip checking the follows list, if it says yes you have to check but the chances are pretty low that it will not be worth the dig

Avatar
the axiom 2y ago

I just did a benchmark and bloom filters are slower than default hashmaps with event ids for this job.