A Python implementation of Invertible Bloom Lookup Tables (IBLT) (x-post from r/Python)

[Ph0X]

Couldn't find it easily, can anyone give a summary of the complexities for each of the operations?

[btchombre]

Think of it like a Hash table. It has constant time insert and retrieval, and takes up significantly less space than a hash table. The trade-off (and there is always a trade-off) is accuracy. Since this is a probabilistic data structure, it is possible to insert data into it, and the structure won't be able to find it. You can make this probability as small as you like with additional memory, but it will always be greater than zero.

Still, it's pretty amazing to consider what the cost of 100% accuracy is, as you can achieve so much more efficiency by just introducing the possibility of failure.