誤り許容カウント法(lossy count method)のサンプルプログラム
誤り許容カウント法(lossy count method)のサンプルプログラム 2010-05-12-1 [Programming][Algorithm] 1行1ラベル形式で、 1万種類のラベルを持つ、 100万行のデータがあるとします （ラベルの頻度分布はジップの法則にだいたい準拠するとします）。 各ラベルの頻度をハッシュを使ってカウントするとなると、ハッシュエントリ1万個分のメモリ容量が必要になります。（1万じゃたいしたことないな、という人はもっと大きな数に置き換えて読んでください。） しかし、カウント後に高頻度のものしか使わないということも多いと思います。例えば頻度5000以上のもののみ取り出してあとはいらない、とか。 そうなると、全部のラベルのカウントデータを最後まで保持するのは無駄に思えます。 そこで登場するのが「誤り許容カウント法(lossy count method)」。 低
Count-Min Sketch のライブラリを公開しました
2012-02-17 Count-Min Sketch のライブラリを公開しました written by Susumu Yata. はじめに 先日 groonga プロジェクトでの利用を目的として開発しているライブラリ Madoka を公開しました．Madoka は Count-Min Sketch という手法をライブラリ化したものであり，文書集合に含まれるキーワードの頻度を求める，クエリの頻度を求める，などの用途に使うことができます． s-yata/madoka - GitHub Documentation - Madoka ライブラリの使い方についてはドキュメントに書いてあるので，こちらは Count-Min Sketch と Madoka の特徴をまとめた内容になっています． Count-Min Sketch 頻度を求めることが目的であれば，ハッシュ表による連想配列を使うのが，おそら
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Count-Min Sketch
https://dl.acm.org/doi/10.5555/1287369.1287400
