202007勉強会資料 ストリームアルゴリズム
- 2. 参考文献 オンラインアルゴリズムとストリームアルゴリズム - https://www.amazon.co.jp/dp/4320121716 Streaming algorithm - https://en.wikipedia.org/wiki/Streaming_algorithm PLAID Tech Blog - https://tech.plaid.co.jp/streaming-algorithm/
- 7. タスク1：最大値 今までの最大値は何か？ 10 15 8 14 10 20 14 18 ??? 6 問題 現在
- 8. チャンピオンアルゴリズム 今までの最大値と現在の値を比較 - 現在の値の方が大きい場合、最大値を入れ替え ストリームアルゴリズムでも正確に計算できる Max: 20 ポイント 10 15 8 14 10 20 14 18 ??? 6 アルゴリズム 現在
- 9. タスク2：頻出データ 過去のデータで、「一定割合」以上出現したデータを抽出したい 正確に求める方法はないため、近似になる => 近似率（=誤差率ε）がパラメータになる a b a a c a a d d a d e f d ポイント ??? 問題 現在
- 10. Lossy Counting 1/ε個ごとのbucketに分割し、各bucketに１回以上出現するもののみカウントする bucket Nの要素Eに対して、<E, 出現回数,許容誤差>を保持 許容誤差 = 過去出現した可能性のある回数 = bucket番号-1 - eが存在する : <E, 回数+1, 許容誤差> - eが存在しない : <E, 1, N-1> bucket切り替え時 : 回数 + n < N の要素を削除 アルゴリズム a b a a c a a d d a d e f d bucket1 bucket2 bucket4bucket3 bucket5 ??? アイデア 現在
- 11. Lossy Counting bucket3での挙動 a b a a c a a d d a d e f d bucket1 bucket2 bucket4bucket3 bucket5 ??? a 4 0 b deleted c 1 1 a 5 0 b deleted c 1 1 a 5 0 b deleted c 1 1 a 4 0 b deleted c 1 1 a 4 0 b deleted c 1 1 a d d d 1 2 d 2 2 bucket 切り替え d 2 2 すでにある要素 = 回数+1 無い要素なら追加 <要素, 1(回数), N-1> 回数+誤差 < N の要素を削除 = 1bucketに平均１回以上出 現してないもの
- 12. KSPアルゴリズム <E, 出現回数, 許容誤差> の代わりに、 <E, 出現回数 - 許容誤差> を保持する アイデア
- 13. タスク3：種類数カウント 出現するデータの種類は何種類あるか a b a a c a a d d a d e f d ??? 問題 現在
- 14. ハッシュ関数を用いた近似カウント ハッシュ関数でbucket分散させて、特定のbucketだけカウントする a hash(E) / 4 = 0 hash(E) / 4 = 1 hash(E) / 4 = 2 hash(E) / 4 = 3 b c f d e ここだけカウント a b a a c a a d d a d e f d ??? アイデア
- 15. ダブリング法 分割数が少ないと、メモリが溢れる ? 分割数が多いと、誤差が大きくなる a hash(E) % 4 = 0 hash(E) % 4 = 1 b c a b c d a b c f d e hash(E) % 2 = 0 hash(E) % 2 = 1 hash(E) % 1 = 0 課題
- 16. ウィンドウ関数 fixed window sliding window 例）日次、週次 7/1 7/2 7/3 7/4 7/5 7/6 7/7 7/8 7/9 7/1 7/2 7/3 7/4 7/5 7/6 7/2 7/3 7/4 7/5 7/6 7/7 7/3 7/4 7/5 7/6 7/7 7/8 例）直近１週間
- 17. タスク4：sliding windowの最大値 今までの最大値は何か？ windowXの最大値は20 windowYの最大値は？18？19があったかもしれない 10 15 8 14 10 20 14 18 windowX windowY ??? 6 問題 ポイント 現在
- 18. sliding window 最大値アルゴリズム 自分より古いものが全て消えた時に最大値になる可能性があるものを残す <時間, 値>のリストを次のルールで保持する - 新しく値Xの要素がくる => リストの中でX以下の要素を全て削除して <current, X> を最後尾に追加 - windowがスライド => 外れた時間の要素を削除 10 15 8 14 10 20 14 18 ??? 6 アルゴリズム アイデア 現在
- 19. sliding window 最大値アルゴリズム 10 15 8 14 10 20 14 18 window1 window2 ??? 6 window3 15 8 14 10 window1 window2 window3 15 8 14 10 20 15 8 14 10 20 6 現在
- 20. さらに省メモリ化 X以下を削除 の部分を X+誤差ε以下のものを削除 にする 誤差ε以内の差の要素は保存しなくなる アイデア