Investor's wiki

블룸 필터

블룸 필터

๋ธ”๋ฃธ ํ•„ํ„ฐ๋Š” ํŠน์ • ํ•ญ๋ชฉ์ด ์ง‘ํ•ฉ์˜ ์ผ๋ถ€์ธ์ง€ ์—ฌ๋ถ€๋ฅผ ์‚ฌ์šฉ์ž์—๊ฒŒ ์•Œ๋ฆฌ๋Š” ๋ฐ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋Š” ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค. ์š”์†Œ๊ฐ€ ์ง‘ํ•ฉ์— ์žˆ๋Š”์ง€ ์—ฌ๋ถ€๋ฅผ ํ™•์‹คํ•˜๊ฒŒ ๋งํ•  ์ˆ˜๋Š” ์—†์ง€๋งŒ ์š”์†Œ๊ฐ€ ์—†๋Š” ๊ฒฝ์šฐ์—๋Š” ํ™•์‹คํ•˜๊ฒŒ ๋งํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

1970๋…„ Burton Howard Bloom์ด ๋งŒ๋“  Bloom ํ•„ํ„ฐ๋Š” ๊ณต๊ฐ„ ์‚ฌ์šฉ์˜ ํšจ์œจ์„ฑ์œผ๋กœ ์ธํ•ด ๋‹ค์–‘ํ•œ ์‘์šฉ ๋ถ„์•ผ์— ๋งค๋ ฅ์ ์ธ ์ œํ’ˆ์ž…๋‹ˆ๋‹ค. ์ผ๋ถ€ ์•”ํ˜ธํ™”ํ(ํŠนํžˆ ๋น„ํŠธ์ฝ”์ธ)์—์„œ๋Š” ๋‹จ์ˆœํ™”๋œ ์ง€๋ถˆ ํ™•์ธ(SPV)์—์„œ ์ค‘์š”ํ•œ ์—ญํ• ์„ ํ•ฉ๋‹ˆ๋‹ค.

SPV ํด๋ผ์ด์–ธํŠธ๋ฅผ ์‚ฌ์šฉํ•˜๋ฉด ์‚ฌ์šฉ์ž๋Š” ์ „์ฒด ๋…ธ๋“œ๋ฅผ ์‹คํ–‰ํ•˜์ง€ ์•Š๊ณ ๋„ ๋น„ํŠธ์ฝ”์ธ ๋„คํŠธ์›Œํฌ์™€ ์ƒํ˜ธ ์ž‘์šฉํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ „์ฒด ๋…ธ๋“œ์—๋Š” ์Šค๋งˆํŠธํฐ๊ณผ ๊ฐ™์€ ์ €์ „๋ ฅ ์žฅ์น˜์—์„œ ์‹คํ–‰ํ•˜๊ธฐ ์–ด๋ ต๊ฒŒ ๋งŒ๋“œ๋Š” ํŠน์ • ์Šคํ† ๋ฆฌ์ง€ ๋ฐ ๊ณ„์‚ฐ ์š”๊ตฌ ์‚ฌํ•ญ์ด ์žˆ์Šต๋‹ˆ๋‹ค. ๋ฐ˜๋ฉด์— SPV ํด๋ผ์ด์–ธํŠธ๋Š” ์‚ฌ์šฉ์ž์˜ ์ง€๊ฐ‘๊ณผ ๊ด€๋ จ๋œ ์ •๋ณด์— ๋Œ€ํ•ด ์ „์ฒด ๋…ธ๋“œ์— ๊ฐ„๋‹จํžˆ ์ฟผ๋ฆฌํ•ฉ๋‹ˆ๋‹ค.

์ด ๋ฐ์ดํ„ฐ๋ฅผ ์‚ฌ์šฉ์ž์—๊ฒŒ ์ „๋‹ฌํ•˜๋Š” ๊ฐ€์žฅ ๊ฐ„๋‹จํ•œ ์†”๋ฃจ์…˜์€ ์ „์ฒด ๋…ธ๋“œ๊ฐ€ ํด๋ผ์ด์–ธํŠธ์˜ ํ‚ค๋ฅผ ์ธ์‹ํ•˜๋„๋ก ํ•˜์—ฌ ์ ์ ˆํ•œ ํŠธ๋žœ์žญ์…˜๋งŒ ์ „์†ก๋˜๋„๋ก ํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. ๋ถ„๋ช…ํžˆ ์ด๊ฒƒ์€ ํด๋ผ์ด์–ธํŠธ์˜ ๊ฐœ์ธ ์ •๋ณด๊ฐ€ ํฌ์ƒ๋  ๊ฒƒ์ด๊ธฐ ๋•Œ๋ฌธ์— ์ˆ˜์ค€ ์ดํ•˜์˜ ์†”๋ฃจ์…˜์ž…๋‹ˆ๋‹ค. ๋ฐ˜๋ฉด์— ๋ชจ๋“  ํŠธ๋žœ์žญ์…˜์„ ๋‹ค์šด๋กœ๋“œํ•˜์—ฌ ๋Œ€๋ถ€๋ถ„์„ ๋ฒ„๋ฆฌ๋Š” ๊ฒƒ์€ ๋Œ€์—ญํญ ๋‚ญ๋น„์ž…๋‹ˆ๋‹ค. ๋ธ”๋ฃธ ํ•„ํ„ฐ๋ฅผ ์ž…๋ ฅํ•ฉ๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด ๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. ํด๋ผ์ด์–ธํŠธ Alice๊ฐ€ ์ „์ฒด ๋…ธ๋“œ๋ฅผ ์‹คํ–‰ํ•˜๋Š” Bob์ด ์ธ์‹ํ•˜์ง€ ์•Š๊ธฐ๋ฅผ ๋ฐ”๋ผ๋Š” ๊ณ ๊ฐ€์น˜ ํŠธ๋žœ์žญ์…˜์„ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค๊ณ  ๊ฐ€์ •ํ•ฉ๋‹ˆ๋‹ค. ๊ทธ๋…€๋Š” 10x1 ๊ทธ๋ฆฌ๋“œ๋กœ ์„ค๋ช…ํ•  Bloom ํ•„ํ„ฐ๋ฅผ ๊ตฌ์„ฑํ•ฉ๋‹ˆ๋‹ค.

๊ทธ๋…€๋Š” ๊ด€์‹ฌ ์žˆ๋Š” ํŠธ๋žœ์žญ์…˜ ๋ฐ์ดํ„ฐ๋ฅผ 0๊ณผ 9 ์‚ฌ์ด์˜ ๋‘ ์ˆซ์ž๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ๋‘ ๊ฐœ์˜ ๋‹ค๋ฅธ ํ•ด์‹œ ํ•จ์ˆ˜๋ฅผ ํ†ตํ•ด ์ „๋‹ฌํ•ฉ๋‹ˆ๋‹ค. ์ด๋ฅผ 4์™€ 7์ด๋ผ๊ณ  ๋ถ€๋ฅด๊ฒ ์Šต๋‹ˆ๋‹ค. ๊ทธ๋…€๋Š” ํ•„ํ„ฐ๋ฅผ Bob์—๊ฒŒ ๋ณด๋ƒ…๋‹ˆ๋‹ค.

์ด ๊ทธ๋ฆฌ๋“œ๋ฅผ ๋ณด๋ฉด Alice๊ฐ€ ํ•„ํ„ฐ์— ์–ด๋–ค ๋ฐ์ดํ„ฐ๋ฅผ ์ „๋‹ฌํ–ˆ๋Š”์ง€ ์•Œ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค. ๋ฐ์ดํ„ฐ๊ฐ€ ํฌํ•จ๋œ ์ง‘ํ•ฉ์ด ์žˆ๋Š” ๊ฒฝ์šฐ ์ด๋ฅผ ํ•ด์‹œํ•˜๊ณ  ํ•„ํ„ฐ์™€ ๋น„๊ตํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ผ์น˜ํ•˜๋Š” ๊ฒฝ์šฐ Alice๊ฐ€ ์š”์ฒญํ•œ ์ •๋ณด์ผ ๊ฐ€๋Šฅ์„ฑ์ด ์žˆ์Šต๋‹ˆ๋‹ค.

๋™์‹œ์— 4์™€ 7์— ๋งคํ•‘๋˜๋Š” ๋งŽ์€ ์ž…๋ ฅ์ด ์žˆ์„ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ Bob์€ Alice๊ฐ€ ๊ด€์‹ฌ์„ ๊ฐ–๊ณ  ์žˆ๋Š” ๋ฐ์ดํ„ฐ ๋ถ€๋ถ„์„ ๊ฒฐ์ •ํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค. ๊ทธ๋Š” ๋‹จ์ˆœํžˆ ๋ชจ๋“  ์ผ์น˜ ํ•ญ๋ชฉ์„ ๋ฐ˜ํ™˜ํ•˜๊ณ  Alice๋Š” ํ•ด๋‹น ํ•ญ๋ชฉ์„ ํ•„ํ„ฐ๋งํ•ฉ๋‹ˆ๋‹ค.

๋ฌผ๋ก  ์ด๊ฒƒ์€ ์ง€๋‚˜์น˜๊ฒŒ ๋‹จ์ˆœํ™”ํ•œ ๊ฒƒ์ด์ง€๋งŒ ๊ฐœ๋…์„ ๋ณด์—ฌ์ค๋‹ˆ๋‹ค. ๋ธ”๋ฃธ ํ•„ํ„ฐ๋Š” ํด๋ผ์ด์–ธํŠธ์˜ ์ง„์ •ํ•œ ์ด์ต์„ ๋‚œ๋…ํ™”ํ•ฉ๋‹ˆ๋‹ค. ์™„๋ฒฝํ•œ ๋ฐฉ๋ฒ•์€ ์•„๋‹ˆ์ง€๋งŒ(์—ฌ์ „ํžˆ ๊ฐœ์ธ ์ •๋ณด ๋ณดํ˜ธ์— ๋Œ€ํ•œ ์šฐ๋ ค๊ฐ€ ์žˆ์Œ) ๋…ธ๋“œ์— ๋Œ€ํ•œ ๋น„์ฐจํ ์š”์ฒญ์— ๋น„ํ•ด ๊ฐœ์„ ๋œ ๊ฒƒ์ž…๋‹ˆ๋‹ค.