# [[Invertible Bloom Filter]]
![[Invertible Bloom Filter.svg]]
An invertible [[Bloom filter]] is a [[Probabilistic Data Structure|probabilistic data structure]] that not only represents group membership like a traditional bloom filter (in that it tells when elements are *probably not* present) but also represents set reconciliation (which elements are different between two sets).
An invertible bloom filter can be explained as an extension of the [[xor]] trick. [^1] Given two sets, A and B, XOR is good at finding one or two elements that are in A and not in B (or vice versa). However, XOR doesn't work as well when there are three or potentially more missing elements. You can use invertible bloom filters to go beyond XOR by introducing two new elements:
- Partitioning of the sets into smaller subsets (using a hashing scheme)
- *Peeling*, a graph algorithm that iteratively recovers the differing elemeents with very high probability.
![[nochlin-invertible-bloom-filters.png]]
Image and caption below from Jason Nochlin. [^1]
_Figure 2: IBF diagram showing a simplified overview of the structure and operations. Each element in the original set is mapped to multiple cells in a bipartite graph. The two IBFs are subtracted, causing like elements to cancel out. Then, the cells are iteratively peeled to recover the symmetric difference._
%%
# Excalidraw Data
## Text Elements
## Drawing
```json
{
"type": "excalidraw",
"version": 2,
"source": "https://github.com/zsviczian/obsidian-excalidraw-plugin/releases/tag/2.1.4",
"elements": [
{
"id": "4y8R7iOA",
"type": "text",
"x": 118.49495565891266,
"y": -333.44393157958984,
"width": 3.8599853515625,
"height": 24,
"angle": 0,
"strokeColor": "#1e1e1e",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 2,
"strokeStyle": "solid",
"roughness": 1,
"opacity": 100,
"groupIds": [],
"frameId": null,
"roundness": null,
"seed": 967149026,
"version": 2,
"versionNonce": 939059582,
"isDeleted": true,
"boundElements": null,
"updated": 1713723615080,
"link": null,
"locked": false,
"text": "",
"rawText": "",
"fontSize": 20,
"fontFamily": 4,
"textAlign": "left",
"verticalAlign": "top",
"containerId": null,
"originalText": "",
"lineHeight": 1.2
}
],
"appState": {
"theme": "dark",
"viewBackgroundColor": "#ffffff",
"currentItemStrokeColor": "#1e1e1e",
"currentItemBackgroundColor": "transparent",
"currentItemFillStyle": "solid",
"currentItemStrokeWidth": 2,
"currentItemStrokeStyle": "solid",
"currentItemRoughness": 1,
"currentItemOpacity": 100,
"currentItemFontFamily": 4,
"currentItemFontSize": 20,
"currentItemTextAlign": "left",
"currentItemStartArrowhead": null,
"currentItemEndArrowhead": "arrow",
"scrollX": 583.2388916015625,
"scrollY": 573.6323852539062,
"zoom": {
"value": 1
},
"currentItemRoundness": "round",
"gridSize": null,
"gridColor": {
"Bold": "#C9C9C9FF",
"Regular": "#EDEDEDFF"
},
"currentStrokeOptions": null,
"previousGridSize": null,
"frameRendering": {
"enabled": true,
"clip": true,
"name": true,
"outline": true
}
},
"files": {}
}
```
%%
[^1]: Nochlin, J. (2025). *Extending that XOR trick to billions of rows - an introduction to invertible bloom filters*. Retrieved in December 2025 from https://nochlin.com/blog/extending-that-xor-trick