%%
date:: [[2024-04-08]]
parent::
%%
# [[Bloom filter]]
A bloom filter is a "space-efficient probabilistic data structure" [^wiki] that is used to determine whether a set of data belongs to a subset. Instead of doing a full lookup of every row in a [[Database]], bloom filters allow you to instead make an educated guess about which sets of data contain the information you're looking for.
The advantage of this approach is that it's faster and more space-efficient because you don't have to store a massive index of all data-- you just have to store "blooms" that hold the pattern. The disadvantage is that it's less accurate. Using bloom filters will tell you whether a certain bit of information:
- is *possibly in the dataset*
- is *definitely not in the dataset*
It is currently used in [[Grafana Loki]] (as of [[Loki 3.0]]) as a way to discard large subsets of data while searching for a specific pattern in a performant way.
![[Bloom filter.svg]]
*An example of a Bloom filter, representing the set {x, y, z} . The colored arrows show the positions in the bit array that each set element is mapped to. The element w is not in the set {x, y, z} , because it hashes to one bit-array position containing 0. For this figure, m = 18 and k = 3.* [^wiki]
[^wiki]: Wikipedia. *Bloom filter*. Retrieved on [[2024-04-08]] from https://en.wikipedia.org/wiki/Bloom_filter
%%
# Excalidraw Data
## Text Elements
## Embedded Files
1a18ff1b7d58e589262a06173122a65d7f217370: [[wiki-bloomfilter.png]]
## Drawing
```json
{
"type": "excalidraw",
"version": 2,
"source": "https://github.com/zsviczian/obsidian-excalidraw-plugin/releases/tag/2.5.0",
"elements": [
{
"id": "9Vh8v07PtG8fWMX12oF8g",
"type": "image",
"x": -463.6360676884651,
"y": -283.50260162353516,
"width": 1280,
"height": 460,
"angle": 0,
"strokeColor": "transparent",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 2,
"strokeStyle": "solid",
"roughness": 1,
"opacity": 100,
"groupIds": [],
"frameId": null,
"index": "a0",
"roundness": null,
"seed": 1733896780,
"version": 5,
"versionNonce": 944198900,
"isDeleted": false,
"boundElements": null,
"updated": 1726661061963,
"link": null,
"locked": false,
"status": "pending",
"fileId": "1a18ff1b7d58e589262a06173122a65d7f217370",
"scale": [
1,
1
]
}
],
"appState": {
"theme": "light",
"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",
"currentItemArrowType": "round",
"scrollX": 532.34375,
"scrollY": 524.4270629882812,
"zoom": {
"value": 1
},
"currentItemRoundness": "round",
"gridSize": 20,
"gridStep": 5,
"gridModeEnabled": false,
"gridColor": {
"Bold": "rgba(217, 217, 217, 0.5)",
"Regular": "rgba(230, 230, 230, 0.5)"
},
"currentStrokeOptions": null,
"frameRendering": {
"enabled": true,
"clip": true,
"name": true,
"outline": true
},
"objectsSnapModeEnabled": false,
"activeTool": {
"type": "selection",
"customType": null,
"locked": false,
"lastActiveTool": null
}
},
"files": {}
}
```
%%