IBLTs(Invertible Bloom Lookup Tables)

IBLTs(Invertible Bloom Lookup Tables)

notion image

subtraction operation : 서로다른 두 집합의 대칭차(symmetric difference)를 구할때 유용함(15%차이)

Bloom Filter와 달리 bit대신 각cell이 count와 key-value 쌍으로 이루어짐

데이터의 삽입, 수정, 삭제가 가능함

IBLT의 크기는 두 집합의 크기와 관계없고, subtraction후 디코딩할수있다고 예상되는 차이에 따라 다름.

notion image

IBLT의 연산

자세한 과정이 궁금하면

Bloom Filter + IBLT 연산 해보기

Insert

notion image

List

notion image

Subtract

notion image

References

Invertible Bloom Lookup Tables

https://arxiv.org/pdf/1101.2245.pdf

Set Reconciliation and File Synchronization Using Invertible Bloom Lookup Tables (자세한 IBLT연산 방법을 이해하는데 도움이 되었던 Paper)

pdfs.semanticscholar.org

https://pdfs.semanticscholar.org/fc29/985a45147961a10dc21c10e1fda53a3c5e42.pdf?_ga=2.68053203.358643043.1556115215-1380938575.1556115215

Codechain에서 IBLT를 소개한 글

Invertible Bloom Lookup Table

Horizontal scalability is one of the most important issues in modern software development. If your program could handle more tasks just by creating more instances of it, life would be much easier. But as you have experienced, it is extremely hard to achieve such kind of scalability in real world.

Invertible Bloom Lookup Table

https://medium.com/codechain/invertible-bloom-lookup-table-37600927cfbe

Invertible Bloom Lookup Table