Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
知っておくと便利な Bloom Filter / Bloom Filter
Search
Yoshiaki Yoshida
October 14, 2016
Technology
2
6.5k
知っておくと便利な Bloom Filter / Bloom Filter
Blog /
https://kakakakakku.hatenablog.com/entry/2016/10/14/220055
Yoshiaki Yoshida
October 14, 2016
Tweet
Share
More Decks by Yoshiaki Yoshida
See All by Yoshiaki Yoshida
技術ブロガーを育てる!ブログメンタリングで何を教えているのか / Passion for Blog Mentoring
kakakakakku
8
37k
プログラミング初心者に教えるときは「身近な比喩」が重要なのだ! / Metaphor is Important for Beginner Programmer
kakakakakku
2
5.6k
プロジェクトの成功を支える ZenHub と モブプログラミング / ZenHub and Mob Programming
kakakakakku
1
5.8k
楽しく!アウトプットを習慣化しよう / Let's Enjoy Output
kakakakakku
3
6.8k
さぁ!今すぐプロジェクトリーダーに立候補しよう / Be a Project Leader
kakakakakku
3
9.1k
プロジェクトをリードする技術 (Kyash 社 再演) / Project Leading is Skill for Kyash
kakakakakku
4
2.1k
プロジェクトをリードする技術 / Project Leading is Skill
kakakakakku
43
47k
Mackerel で ECS をどこまでモニタリングできるのか / Monitoring ECS with Mackerel
kakakakakku
0
13k
[2018/01/30] Redash 初心者向けハンズオン / Redash Meetup #0.1
kakakakakku
0
2.4k
Other Decks in Technology
See All in Technology
CSS、JSをHTMLテンプレートにまとめるフロントエンド戦略
d120145
0
290
実践! AIエージェント導入記
1mono2prod
0
160
M3 Expressiveの思想に迫る
chnotchy
0
100
標準技術と独自システムで作る「つらくない」SaaS アカウント管理 / Effortless SaaS Account Management with Standard Technologies & Custom Systems
yuyatakeyama
3
1.2k
Amazon Bedrockで実現する 新たな学習体験
kzkmaeda
1
530
Github Copilot エージェントモードで試してみた
ochtum
0
100
250627 関西Ruby会議08 前夜祭 RejectKaigi「DJ on Ruby Ver.0.1」
msykd
PRO
2
260
A2Aのクライアントを自作する
rynsuke
1
170
生成AIでwebアプリケーションを作ってみた
tajimon
2
140
20250625 Snowflake Summit 2025活用事例 レポート / Nowcast Snowflake Summit 2025 Case Study Report
kkuv
1
310
Fabric + Databricks 2025.6 の最新情報ピックアップ
ryomaru0825
1
130
Snowflake Summit 2025全体振り返り / Snowflake Summit 2025 Overall Review
mtpooh
2
390
Featured
See All Featured
Designing for Performance
lara
609
69k
Let's Do A Bunch of Simple Stuff to Make Websites Faster
chriscoyier
507
140k
The Invisible Side of Design
smashingmag
299
51k
StorybookのUI Testing Handbookを読んだ
zakiyama
30
5.8k
Side Projects
sachag
455
42k
The Cult of Friendly URLs
andyhume
79
6.5k
10 Git Anti Patterns You Should be Aware of
lemiorhan
PRO
657
60k
KATA
mclloyd
29
14k
The Web Performance Landscape in 2024 [PerfNow 2024]
tammyeverts
8
670
Principles of Awesome APIs and How to Build Them.
keavy
126
17k
Measuring & Analyzing Core Web Vitals
bluesmoon
7
490
Documentation Writing (for coders)
carmenintech
72
4.9k
Transcript
͓ͬͯ͘ͱศརͳ Bloom Filter 2016-10-14 ࣾษڧձ @kakakakakku
Bloom Filter • 1970ʹߟҊ͞Εͨ • ߟҊऀ Burton Howard Bloom ࢯ
• ۭؒޮͷྑ͍֬తσʔλߏ • ཁૉ͕ू߹ͷதʹؚ·ΕΔ͔Λఆ͢ΔͨΊʹ͏ • σʔλྔʹґଘͤͣ O(k) ͷܭࢉྔͰߴʹఆͰ͖Δ
ू߹ ؚ·ΕΔ? ؚ·Εͳ͍? ؚ·ΕΔ? ؚ·Εͳ͍?
׆༻ྫΛΕ Bloom Filter Λ ͬͱۙʹײ͡ΒΕΔͣʂ
• Cassandra • Key Λݕࡧ͢Δͱ͖ͷ I/O Λݮ͢ΔͨΊ SSTable ʹ Bloom
Filter Λॻ͖ࠐΜͰ͍Δ • HBase • HFile ʹಛఆͷσʔλؚ͕·Ε͍ͯͳ͍͜ͱΛ ݕࡧ͢ΔͨΊʹ Bloom Filter Λ׆༻͍ͯ͠Δ Bloom Filter ׆༻ྫ 1
Bloom Filter ׆༻ྫ 2 • H2O • ແବͳαʔόϓογϡΛૹ৴͠ͳ͍ͨΊʹ ϒϥβΩϟογϡใͷ Bloom
Filter Λ ѹॖͯ͠ HTTP Ͱฦ͍ͯ͠Δ CASPER (Cache-Aware Server PushER) • Bitcoin • τϥϯβΫγϣϯͷݕࡧʹ׆༻͍ͯ͠Δ? ʢৄ֬͘͠ೝͰ͖ͯͳ͍ʣ
Bloom Filter ׆༻ྫ 3 • pixiv • ࡞ʹ͍ͨλάͱ pixiv ඦՊࣄయͷλάू߹ͷ
ଘࡏ֬ೝʹ׆༻͍ͯ͠Δ? http://inside.pixiv.net/entry/2014/07/22/132103
ʘ Bloom Filter ͷڍಈ ʗ
0 0 1 0 2 0 3 0 4 0
5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 • m bit ͷྻΛ༻ҙ͢Δ • ࠓճ ྻۭؒ = m = 16 ͱ͢Δ • શͯ 0 ͰॳظԽ͓ͯ͘͠
0 0 1 0 2 0 3 0 4 0
5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 • ҙͷϋογϡؔΛ༻ҙ͢Δ • ࠓճ k = 2 ݸͷؔΛ͏ • h1(key) = (key * 1) mod m • h2(key) = (key * 2) mod m
0 1 1 0 2 0 3 0 4 0
5 0 6 0 7 0 8 1 9 0 10 0 11 0 12 0 13 0 14 0 15 0 • key = 1000 ΛՃ͢Δ • h1(1000) = 8 • h2(1000) = 0 [ 1000 ]
0 1 1 0 2 1 3 0 4 0
5 0 6 0 7 0 8 1 9 1 10 0 11 0 12 0 13 0 14 0 15 0 • key = 1001 ΛՃ͢Δ • h1(1001) = 9 • h2(1001) = 2 [ 1000, 1001 ]
0 1 1 0 2 1 3 0 4 0
5 0 6 0 7 0 8 1 9 1 10 0 11 0 12 1 13 0 14 0 15 0 • key = 1004 ΛՃ͢Δ • h1(1004) = 12 • h2(1004) = 8 • h1(1000) = 8 ͱॏෳ͍ͯ͠Δ • ϑϥά 1 ͷ··ʹ͢Δ [ 1000, 1001, 1004 ]
0 1 1 0 2 1 3 0 4 0
5 0 6 0 7 0 8 1 9 1 10 0 11 0 12 1 13 0 14 0 15 0 • Query : key = 1005 ଘࡏ͢Δ ? • h1(1005) = 13 • h2(1005) = 10 • h1(1005) = h2(1005) = 0 • ʮଘࡏ͠ͳ͍ʯͱஅݴͰ͖Δ [ 1000, 1001, 1004 ]
0 1 1 0 2 1 3 0 4 0
5 0 6 0 7 0 8 1 9 1 10 0 11 0 12 1 13 0 14 0 15 0 • Query : key = 1000 ଘࡏ͢Δ ? • h1(1000) = 8 • h2(1000) = 0 • h1(1000) = h2(1000) = 1 • ʮଘࡏ͢Δʯ͔͠Εͳ͍ • 1000 ࣮ࡍʹଘࡏ͢Δ [ 1000, 1001, 1004 ]
0 1 1 0 2 1 3 0 4 0
5 0 6 0 7 0 8 1 9 1 10 0 11 0 12 1 13 0 14 0 15 0 • Query : key = 1020 ଘࡏ͢Δ ? • h1(1020) = 12 • h2(1020) = 8 • h1(1000) = h2(1000) = 1 • ʮଘࡏ͢Δʯ͔͠Εͳ͍ • 1020 ࣮ࡍʹଘࡏ͠ͳ͍ [ 1000, 1001, 1004 ]
(ƅшƅ) Űō? ޡఆͯ͠Δ͚Ͳ…?
False Positive ِཅੑ False Negative ِӄੑ ʮଘࡏ͠ͳ͍ʯͱ͖ʹʮଘࡏ͢Δʯͱఆͯ͠͠·͏͜ͱ ʮଘࡏ͢Δʯͱ͖ʹʮଘࡏ͠ͳ͍ʯͱఆͯ͠͠·͏͜ͱ
False Positive ِཅੑ False Negative ِӄੑ ʮଘࡏ͠ͳ͍ʯͱ͖ʹʮଘࡏ͢Δʯͱఆͯ͠͠·͏͜ͱ ʮଘࡏ͢Δʯͱ͖ʹʮଘࡏ͠ͳ͍ʯͱఆͯ͠͠·͏͜ͱ ↑ Bloom
Filter ʹ False Positive ͷՄೳੑ͕͋Δ
False Positive ͷՄೳੑ • O(k) ͰߴʹఆͰ͖Δঈͱͯ͠ False Positive ͷՄೳੑ͕͋Δ •
Αͬͯ key = 1020 ͷΑ͏ʹ ʮଘࡏ͢Δʯͱޡݕͯ͠͠·͏߹͕͋Δ • ͨͩ͠ False Negative 100% ͋Γಘͳ͍
ϝϦοτ • ܭࢉྔ O(k) • ઢܗ୳ࡧͩͱ O(N) • ೋ୳ࡧͩͱ O(log
N) • ϋογϡςʔϒϧͳΒ O(1) ͩͬ͠ͱߴ? • k = 1 ͳΒ Bloom Filter O(1) ʹͳΔ • σʔλΛอ࣋͢Δඞཁ͕ͳۭؒ͘ޮ͕ྑ͍
ʘ Bloom Filter ཁૉ͕আͰ͖ͳ͍ ʗ
0 0 1 0 2 1 3 0 4 0
5 0 6 0 7 0 8 0 9 1 10 0 11 0 12 1 13 0 14 0 15 0 • 1000 Λআ͢Δͱ • h1(1005) = 8 • h2(1005) = 0 • 1004 আ͞Εͯ͠·͏ !!! • h1(1005) = 12 • h2(1005) = 8 [ 1000, 1001, 1004 ]
ʘ ཁૉΛআ͢ΔͳΒ Counting Filter ʗ Bloom Filter Λ֦ுͨ͠ΞϧΰϦζϜ
0 1 1 0 2 0 3 0 4 0
5 0 6 0 7 0 8 1 9 0 10 0 11 0 12 0 13 0 14 0 15 0 • key = 1000 ΛՃ͢Δ • h1(1000) = 8 • h2(1000) = 0 [ 1000 ]
0 1 1 0 2 1 3 0 4 0
5 0 6 0 7 0 8 1 9 1 10 0 11 0 12 0 13 0 14 0 15 0 • key = 1001 ΛՃ͢Δ • h1(1001) = 9 • h2(1001) = 2 [ 1000, 1001 ]
0 1 1 0 2 1 3 0 4 0
5 0 6 0 7 0 8 2 9 1 10 0 11 0 12 1 13 0 14 0 15 0 • key = 1004 ΛՃ͢Δ • h1(1004) = 12 • h2(1004) = 8 • ॏෳͨ͠ΒΠϯΫϦϝϯτ͢Δ [ 1000, 1001, 1004 ] ϏοτͰͳ͘ ΧϯλʔͰදݱ͢Δ͕ Bloom Filter ͱҟͳΔ
0 0 1 0 2 1 3 0 4 0
5 0 6 0 7 0 8 1 9 1 10 0 11 0 12 1 13 0 14 0 15 0 • key = 1000 Λআ͢Δ • h1(1004) = 8 • h2(1004) = 0 • σΫϦϝϯτ͢Δ [ 1000, 1001, 1004 ]
ʘ False Positive ֬ ʗ
Bloom Filter ެࣜͰࢉग़ m : ྻۭؒ (bit) n : ొཁૉ
ৄ͘͠ Wikipedia ʹʂ https://ja.wikipedia.org/wiki/ϒϧʔϜϑΟϧλ False Positive Λ࠷খʹ͢Δ ࠷దͳϋογϡؔͷۙࣅ ࠷దͳ k Λͬͨ߹ͷ False Positive ֬
ʘ ৺ແ༻ ʗ ࠷దͳ k Λ͑ False Positive ΛݶΓͳ͘͘Ͱ͖Δ
ʘ ·ͱΊ ʗ False Positive ͷՄೳੑ͋Δ͠ ཁૉͷআͰ͖ͳ͍͚Ͳ τϨʔυΦϑΛ࠷େݶ׆༻ͯ͠ ߴ &
ۭؒޮͷྑ͍ॲཧ͕Ͱ͖Δʂ
ʘ ͓ͬͯ͘ͱศརͳ Bloom Filter ʗ