Bloom-Filter-diagram.excalidraw
==⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠==
Bloom Filter — Bit Array and Hash Function Diagram
Text Elements
m-bit array ^array-label
0 ^b0 1 ^b1 0 ^b2 1 ^b3 0 ^b4 1 ^b5 0 ^b6 1 ^b7 0 ^b8 0 ^b9 1 ^b10 0 ^b11
element "x" ^x-label h1 ^h1-label h2 ^h2-label h3 ^h3-label
element "y" ^y-label Definitely NOT in set ^not-in-set
False positive possible (all bits set by other elements), false negative impossible ^fp-text
Parameters: m = bits, k = hash functions, n = items ^params-text FPR ~ (1 - e^(-kn/m))^k ^formula-text
%%
Drawing
{
"type": "excalidraw",
"version": 2,
"source": "https://excalidraw.com",
"elements": [
{
"id": "title",
"type": "text",
"x": 60,
"y": 10,
"width": 500,
"height": 24,
"text": "Bloom Filter — Bit Array",
"fontSize": 18,
"fontFamily": 1,
"textAlign": "center",
"verticalAlign": "top",
"strokeColor": "#1e1e1e",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "array-label",
"type": "text",
"x": 60,
"y": 170,
"width": 100,
"height": 20,
"text": "m-bit array",
"fontSize": 13,
"fontFamily": 1,
"textAlign": "left",
"verticalAlign": "middle",
"strokeColor": "#1e1e1e",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "bit0",
"type": "rectangle",
"x": 160,
"y": 160,
"width": 36,
"height": 36,
"strokeColor": "#868e96",
"backgroundColor": "#f8f9fa",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "bit0-text",
"type": "text",
"x": 173,
"y": 170,
"width": 10,
"height": 16,
"text": "0",
"fontSize": 12,
"fontFamily": 1,
"textAlign": "center",
"verticalAlign": "middle",
"strokeColor": "#868e96",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "bit1",
"type": "rectangle",
"x": 196,
"y": 160,
"width": 36,
"height": 36,
"strokeColor": "#2f9e44",
"backgroundColor": "#ebfbee",
"fillStyle": "solid",
"strokeWidth": 2,
"roughness": 1,
"opacity": 100
},
{
"id": "bit1-text",
"type": "text",
"x": 209,
"y": 170,
"width": 10,
"height": 16,
"text": "1",
"fontSize": 12,
"fontFamily": 1,
"textAlign": "center",
"verticalAlign": "middle",
"strokeColor": "#2f9e44",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "bit2",
"type": "rectangle",
"x": 232,
"y": 160,
"width": 36,
"height": 36,
"strokeColor": "#868e96",
"backgroundColor": "#f8f9fa",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "bit2-text",
"type": "text",
"x": 245,
"y": 170,
"width": 10,
"height": 16,
"text": "0",
"fontSize": 12,
"fontFamily": 1,
"textAlign": "center",
"verticalAlign": "middle",
"strokeColor": "#868e96",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "bit3",
"type": "rectangle",
"x": 268,
"y": 160,
"width": 36,
"height": 36,
"strokeColor": "#2f9e44",
"backgroundColor": "#ebfbee",
"fillStyle": "solid",
"strokeWidth": 2,
"roughness": 1,
"opacity": 100
},
{
"id": "bit3-text",
"type": "text",
"x": 281,
"y": 170,
"width": 10,
"height": 16,
"text": "1",
"fontSize": 12,
"fontFamily": 1,
"textAlign": "center",
"verticalAlign": "middle",
"strokeColor": "#2f9e44",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "bit4",
"type": "rectangle",
"x": 304,
"y": 160,
"width": 36,
"height": 36,
"strokeColor": "#868e96",
"backgroundColor": "#f8f9fa",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "bit4-text",
"type": "text",
"x": 317,
"y": 170,
"width": 10,
"height": 16,
"text": "0",
"fontSize": 12,
"fontFamily": 1,
"textAlign": "center",
"verticalAlign": "middle",
"strokeColor": "#868e96",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "bit5",
"type": "rectangle",
"x": 340,
"y": 160,
"width": 36,
"height": 36,
"strokeColor": "#2f9e44",
"backgroundColor": "#ebfbee",
"fillStyle": "solid",
"strokeWidth": 2,
"roughness": 1,
"opacity": 100
},
{
"id": "bit5-text",
"type": "text",
"x": 353,
"y": 170,
"width": 10,
"height": 16,
"text": "1",
"fontSize": 12,
"fontFamily": 1,
"textAlign": "center",
"verticalAlign": "middle",
"strokeColor": "#2f9e44",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "bit6",
"type": "rectangle",
"x": 376,
"y": 160,
"width": 36,
"height": 36,
"strokeColor": "#868e96",
"backgroundColor": "#f8f9fa",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "bit6-text",
"type": "text",
"x": 389,
"y": 170,
"width": 10,
"height": 16,
"text": "0",
"fontSize": 12,
"fontFamily": 1,
"textAlign": "center",
"verticalAlign": "middle",
"strokeColor": "#868e96",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "bit7",
"type": "rectangle",
"x": 412,
"y": 160,
"width": 36,
"height": 36,
"strokeColor": "#2f9e44",
"backgroundColor": "#ebfbee",
"fillStyle": "solid",
"strokeWidth": 2,
"roughness": 1,
"opacity": 100
},
{
"id": "bit7-text",
"type": "text",
"x": 425,
"y": 170,
"width": 10,
"height": 16,
"text": "1",
"fontSize": 12,
"fontFamily": 1,
"textAlign": "center",
"verticalAlign": "middle",
"strokeColor": "#2f9e44",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "bit8",
"type": "rectangle",
"x": 448,
"y": 160,
"width": 36,
"height": 36,
"strokeColor": "#868e96",
"backgroundColor": "#f8f9fa",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "bit8-text",
"type": "text",
"x": 461,
"y": 170,
"width": 10,
"height": 16,
"text": "0",
"fontSize": 12,
"fontFamily": 1,
"textAlign": "center",
"verticalAlign": "middle",
"strokeColor": "#868e96",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "bit9",
"type": "rectangle",
"x": 484,
"y": 160,
"width": 36,
"height": 36,
"strokeColor": "#868e96",
"backgroundColor": "#f8f9fa",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "bit9-text",
"type": "text",
"x": 497,
"y": 170,
"width": 10,
"height": 16,
"text": "0",
"fontSize": 12,
"fontFamily": 1,
"textAlign": "center",
"verticalAlign": "middle",
"strokeColor": "#868e96",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "bit10",
"type": "rectangle",
"x": 520,
"y": 160,
"width": 36,
"height": 36,
"strokeColor": "#2f9e44",
"backgroundColor": "#ebfbee",
"fillStyle": "solid",
"strokeWidth": 2,
"roughness": 1,
"opacity": 100
},
{
"id": "bit10-text",
"type": "text",
"x": 533,
"y": 170,
"width": 10,
"height": 16,
"text": "1",
"fontSize": 12,
"fontFamily": 1,
"textAlign": "center",
"verticalAlign": "middle",
"strokeColor": "#2f9e44",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "bit11",
"type": "rectangle",
"x": 556,
"y": 160,
"width": 36,
"height": 36,
"strokeColor": "#868e96",
"backgroundColor": "#f8f9fa",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "bit11-text",
"type": "text",
"x": 569,
"y": 170,
"width": 10,
"height": 16,
"text": "0",
"fontSize": 12,
"fontFamily": 1,
"textAlign": "center",
"verticalAlign": "middle",
"strokeColor": "#868e96",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "x-box",
"type": "rectangle",
"x": 230,
"y": 50,
"width": 60,
"height": 36,
"strokeColor": "#1971c2",
"backgroundColor": "#d0ebff",
"fillStyle": "solid",
"strokeWidth": 2,
"roughness": 1,
"opacity": 100
},
{
"id": "x-text",
"type": "text",
"x": 248,
"y": 60,
"width": 24,
"height": 20,
"text": "\"x\"",
"fontSize": 13,
"fontFamily": 1,
"textAlign": "center",
"verticalAlign": "middle",
"strokeColor": "#1971c2",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "h1-arrow",
"type": "arrow",
"x": 248,
"y": 86,
"width": -32,
"height": 74,
"strokeColor": "#1971c2",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100,
"points": [[0, 0], [-32, 74]],
"startArrowhead": null,
"endArrowhead": "arrow",
"label": {
"text": "h1",
"fontSize": 11,
"strokeColor": "#1971c2"
}
},
{
"id": "h2-arrow",
"type": "arrow",
"x": 260,
"y": 86,
"width": 48,
"height": 74,
"strokeColor": "#1971c2",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100,
"points": [[0, 0], [48, 74]],
"startArrowhead": null,
"endArrowhead": "arrow",
"label": {
"text": "h2",
"fontSize": 11,
"strokeColor": "#1971c2"
}
},
{
"id": "h3-arrow",
"type": "arrow",
"x": 260,
"y": 86,
"width": 152,
"height": 74,
"strokeColor": "#1971c2",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100,
"points": [[0, 0], [152, 74]],
"startArrowhead": null,
"endArrowhead": "arrow",
"label": {
"text": "h3",
"fontSize": 11,
"strokeColor": "#1971c2"
}
},
{
"id": "y-box",
"type": "rectangle",
"x": 440,
"y": 50,
"width": 60,
"height": 36,
"strokeColor": "#e03131",
"backgroundColor": "#ffe3e3",
"fillStyle": "solid",
"strokeWidth": 2,
"roughness": 1,
"opacity": 100
},
{
"id": "y-text",
"type": "text",
"x": 458,
"y": 60,
"width": 24,
"height": 20,
"text": "\"y\"",
"fontSize": 13,
"fontFamily": 1,
"textAlign": "center",
"verticalAlign": "middle",
"strokeColor": "#e03131",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "yh1-arrow",
"type": "arrow",
"x": 458,
"y": 86,
"width": -52,
"height": 74,
"strokeColor": "#e03131",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100,
"points": [[0, 0], [-52, 74]],
"startArrowhead": null,
"endArrowhead": "arrow"
},
{
"id": "yh2-arrow",
"type": "arrow",
"x": 470,
"y": 86,
"width": -16,
"height": 74,
"strokeColor": "#e03131",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100,
"points": [[0, 0], [-16, 74]],
"startArrowhead": null,
"endArrowhead": "arrow"
},
{
"id": "yh3-arrow",
"type": "arrow",
"x": 480,
"y": 86,
"width": 62,
"height": 74,
"strokeColor": "#868e96",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"strokeStyle": "dashed",
"opacity": 100,
"points": [[0, 0], [62, 74]],
"startArrowhead": null,
"endArrowhead": "arrow"
},
{
"id": "not-in-set-text",
"type": "text",
"x": 560,
"y": 50,
"width": 180,
"height": 36,
"text": "Definitely NOT in set\n(one bit is 0)",
"fontSize": 12,
"fontFamily": 1,
"textAlign": "left",
"verticalAlign": "middle",
"strokeColor": "#868e96",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "fp-text",
"type": "text",
"x": 60,
"y": 220,
"width": 560,
"height": 36,
"text": "False positive possible (all bits set by other elements),\nfalse negative impossible",
"fontSize": 12,
"fontFamily": 1,
"textAlign": "center",
"verticalAlign": "top",
"strokeColor": "#1e1e1e",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "params-box",
"type": "rectangle",
"x": 60,
"y": 278,
"width": 420,
"height": 56,
"strokeColor": "#5c5f66",
"backgroundColor": "#f8f9fa",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "params-title",
"type": "text",
"x": 70,
"y": 286,
"width": 400,
"height": 20,
"text": "Parameters: m = bits, k = hash functions, n = items",
"fontSize": 12,
"fontFamily": 1,
"textAlign": "center",
"verticalAlign": "middle",
"strokeColor": "#5c5f66",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
},
{
"id": "formula-text",
"type": "text",
"x": 70,
"y": 308,
"width": 400,
"height": 20,
"text": "FPR ~ (1 - e^(-kn/m))^k",
"fontSize": 12,
"fontFamily": 1,
"textAlign": "center",
"verticalAlign": "middle",
"strokeColor": "#1971c2",
"backgroundColor": "transparent",
"fillStyle": "solid",
"strokeWidth": 1,
"roughness": 1,
"opacity": 100
}
],
"appState": {
"gridSize": null,
"viewBackgroundColor": "#ffffff"
},
"files": {}
}%%