search

ssbc / ssb-db2

A new database for secure-scuttlebutt
47 stars 8 forks source link

Bloom something #147

Open staltz opened 3 years ago

staltz commented 3 years ago

Not sure if we can/should use bloom filters, but this library looks good and supports export/import to JSON string. https://callidon.github.io/bloom-filters/

staltz commented 3 years ago

Like, prefix indexes are basically similar to bloom filters, because they behave the same regarding false positives. But maybe we could have a bloom filter for "I follow X" foreach X and another for "I block X" foreach X. Maaaybe. But there are also other data structures there.

arj03 commented 3 years ago

Yes that library is very interesting. Will have a look when I get better time :)

arj03 commented 3 years ago

I was reading up on the idea of learned index (wierd name for what it is), there is an implementation of it here. Basically another index form that could be useful in some specific cases. From this HN discussion.

staltz commented 3 years ago

I was reading up on the idea of learned index (wierd name for what it is), there is an implementation of it here. Basically another index form that could be useful in some specific cases. From this HN discussion.

So cool.

arj03 commented 3 years ago

I was reading up on set replication and was reading Kleppmann's algorithm for this. It has this interesting graph:

image

That said, it seems the graph is based on 10bit truncation.

arj03 commented 3 years ago

Hah, I'm trying to run his python script on 32 bits and I think there is a hidden crypto miner in there, or it's just very inefficient. There is a very big difference between 32 and 10.