| 大会名称 |
|---|
| 2023年 総合大会 |
| 大会コ－ド |
| 2023G |
| 開催年 |
| 2023 |
| 発行日 |
| 2023-02-28 |
| セッション番号 |
| D-1 |
| セッション名 |
| コンピュテーション |
| 講演日 |
| 2023/3/10 |
| 講演場所(会議室等) |
| 2号館 2208教室 |
| 講演番号 |
| D-1-9 |
| タイトル |
| Fast Partitioned Learned Bloom Filter |
| 著者名 |
| ◎佐藤篤樹, 松井勇佑, |
| キーワード |
| アルゴリズムとデータ構造 |
| 抄録 |
| Bloom Filterは近似メンバーシップクエリのための省メモリなデータ構造で，幅広いコンピューティングの分野で活用されている．Partitioned Learned Bloom Filter（PLBF）は，機械学習モデルが捉えた分布の情報を効果的に近似メンバーシップクエリに活用できる新しいBloom Filterである．一方で，PLBFは構築に要する時間計算量が大きいという問題がある．そこで我々は，PLBFと全く同じデータ構造を小さい計算量で構築できるFast PLBFを提案した．また，分布がある制約を満たす時にはPLBFと同じデータ構造となる，さらに小さい計算量で構築できるFast PLBF++を提案した．そして，実験的に(i) Fast PLBFがPLBFよりも，Fast PLBF++がFast PLBFよりも高速に構築できること(ii) Fast PLBFとFast PLBF++がPLBFと同等のメモリ効率を達成できることを示した． |
| 本文pdf |
|
PDF download
|