確率的データ構造は少ないメモリでデータをコンパクトに保存し、保存されたデータに関するクエリに対し、おおよその答えを提供してくれます。クエリに対し空間効率の良い方法で答えるように設計されており、それはつまり、正確さを犠牲にするということにもなります。しかし、これらは一般的に、問われているデータ構造の仕様にもよりますが、誤差率の保証と境界を提供してくれます。メモリ使用量が少ないため、確率的データ構造はストリーミングや低出力の設定に特に有用なのです。ですから、動画の視聴回数を数えたり、過去に投稿された一意となるツイートのリストを維持したりするなど、ビッグデータの環境下では非常に有用です。例えば、 HyperLogLog++ 構造 は、2.56KBのメモリで最大790億の一意のアイテムを数えることができるのですが、誤差率はわずか1.65パーセントです。 Fast Forward Labsのチームは
![確率的データ構造の比較:カッコウフィルタ対ブルームフィルタ | POSTD](https://cdn-ak-scissors.b.st-hatena.com/image/square/bdbe6f238224d636cfe7b88dfafcbaf52714e44f/height=288;version=1;width=512/https%3A%2F%2Fpostd.cc%2Fwp%2Fwp-content%2Fuploads%2F2016%2F12%2Ftumblr_inline_oh29g1UjZy1qcg73w_500-500x201.png)