本文为摘录，原文为： ../pdf/d/p1311-even.pdf

1 Abstract

2 INTRODUCTION

  • What is a filter

    属于近似查询 (approximate membership query), 用于判断独具是否在集合中。

    • 如果输入在集合中，则必定输出 Yes
    • 如果不在集合中，则输出 Yes 的概率不能多于 \(\Sigma\)
  • What are filters used for
    • 与精确查询相比
      • 更省资源， 与数据量无关，而与 Σ （误报率）有关
      • 适于放在内存中，用于真正操作之前来过滤掉无效数据
        • 比如 join