考えれば当たり前だけど確率的データ構造は具体的なデータを扱うシーンってなくて、「存在するか否か」「範囲に含まれる個数」「どのくらい重複があるか」みたいな統計的な情報を得るものが多いな

Reply to this note

Please Login to reply.

Discussion

「存在するか否か」「範囲に含まれる個数」「どのくらい重複があるか」みたいな統計的な情報を得るために、確率的データ構造が用意された、と因果関係をひっくり返してもよろしいでしょうか?

どうでしょう、そう言い切るのは難しいかもしれません。現在の確率的データ構造の主要なユースケースがmap/reduceなどのビッグデータなようなのでそういう側面は強いと思いますが、古典的なアルゴリズムはパフォーマンス上の制約をクリアするニュアンスが強いように思います (主観です)

ブルームフィルタなんかは、正確性よりも性能を優先するために、統計「的」な有意性によりデータ構造を圧縮するアルゴリズムと解釈できるのかななど思いましたが、前からそう思ってたわけではなく、初めのノートを見て思った次第です