問題タブ [streaming-algorithm]

元の質問は、前日にアクセスされた 5 GB の URL を含むファイルが与えられ、上位 k の頻繁な URL を見つけます。この問題は、ハッシュ マップを使用して個別の URL の出現をカウントし、O(n log k) 時間かかる最小ヒープを使用して上位 k を見つけることで解決できます。

入力が (静的ファイルではなく) 無制限のオンライン データ ストリームである場合、どうすれば最終日の上位 k URL を知ることができるでしょうか?

または、最後の分、最後の日、および最後の時間の上位 k URL を動的に取得できるシステムに改善できる点はありますか?

ヒントをいただければ幸いです!!

特定のデータストリーム (〜 100k 値/秒) からの 1 分間のスライディング ウィンドウから一連の値を効率的に維持する方法を探しています。

最大で対数の挿入時間を持つソリューションを探しています (値の基本的な時系列ベクトルには o(n) があるため)

2 つのストリームがstreamAありstreamBます。それぞれにstreamAID があり、一致するイベントにstreamBは同じ ID があります。

たとえば、1 分間のスライディング ウィンドウの後、streamAどの ID からの ID が入っていないかを知りたいです。streamB

私はこれを試しましたが、うまくいきませんでした:

from streamA as A join streamB#window.time(1 min) as B on A.id == B.id select S.Id insert expired events into streamC;

これを解決する方法を教えてください。

ヘビーヒッター向けの次のアルゴリズムを知っています。

間違っている場合は訂正してください。ただし、このアルゴリズムは O(n) では実行されません。O(1/epsilon) のスペース使用を維持しながら、O(n) で実行されるようにこのアルゴリズムを変更することは可能ですか?

データ ストリームの場合、アルゴリズムのポイントは、上位の epsilon*t 項目を返すことです。イプシロンはパーセンテージで与えられます (例: 少なくとも 10% の確率で発生するデータの場合、0.1 を入力)。