Age-Partitioned Bloom Filters
概要
add(e): 要素 e を挿入する
query(e): 要素 e が挿入済みであれば yes、そうでなければ no を返す。false positive (挿入していない要素について yes を返す）をある確率で許容する
この拡張として、直近 w 個の要素が挿入されたかどうかを記憶し、それ以前に挿入された要素を忘れる（"忘れた" 要素について query されたら no を与える）ような確率的データ構造を、Bloom Filter を元に提案した。
モデル
著者らが提案したモデルは以下の通り。
ストリームから要素を順に挿入していくとする。パラメータ
$ w: ストリームにおいて、要素の挿入を記憶している範囲 (window) の幅。
$ s: ストリームにおけて、要素の挿入を忘却している (transition zone) の幅。
$ p:
$ e: 偽陽性確率の上界。