3

特定のプロジェクトについて、いくつかのイベントのデータを取得し、同時にそれらのイベントに関する変数を収集します。データが収集された後、ユーザーが関心を持っているものが何であれ、そのデータに対してユーザーがカスタマイズ可能な分析を実行します。

データは次のような形式で収集されます。

タイムスタンプイベント
0 x = 0
0 y = 1
3イベントAが発生しました
3 x = 1
4イベントAが発生しました
4 x = 2
9イベントBが発生しました
9 y = 2
9 x = 0

いつでも状態全体を理解するための最も簡単なアプローチは、データセット全体をウォークスルーすることです。たとえば、時刻0から開始し、タイムスタンプ5まで「分析」すると、その時点でx = 2、y = 1であり、イベントAが2回発生したことがわかります。これは本当に簡単な例です。ユーザーは、たとえばAからBまでのイベント間の時間に関心がある可能性があり(多くの場合、関心があります)、Aの最初の発生、次にB、またはAの最後の発生、​​次にB(それぞれ、9-3)を指定する可能性があります。 =6または9-4=5)。私が言ったように、これはあなたがセット全体を歩いているときに分析するのは簡単です。

次に、任意の時間枠を分析するためにモデルを適応させる必要があります。0-Nを見ると、それは簡単なケースです。しかし、たとえば1-5を見ると、0から始めて、yが最初は1であり、ウィンドウ1-5で変更されていないことがわからない限り、yの概念はありません。

私たちのアプローチは、基本的に変数のディクショナリを作成し、イベントに対してコールバックを実行することです。1つの分析が「イベントAが発生し、時間が3より大きい場合のxとは」である場合、最初のイベントAでそのコールバックを実行し、時間が3以下であるため、すぐに戻ります。4で再び実行されます。そして、t=4でxが1であったことを報告します。

「タイムウィンドウ」に適応するために、私は(バックグラウンドで)分析に追加の条件に取り組むつもりだと思います。分析が「イベントAが発生したときのxとは」であり、現在のウィンドウが1〜5の場合、「イベントAが発生して時間>=1かつ時間<=5のときのxとは」に変更します。次に、次のウィンドウが6〜10の場合、必要に応じて条件を再調整できます。

私の主な質問は、これはどのようなパターンに合うのかということです。 私たちは明らかにこのような問題に最初に取り組んだ人ではありませんが、他の人がどのように問題に取り組んだかを知ることはできませんでした。私はおそらくGoogleで何を検索するのか正確にはわからないでしょう。 特定の時間に単一の状態を検索するために、グローバル状態全体の辞書を保持する以外に、他のアプローチはありますか? また、データには数、場合によっては数万のレコードが含まれる可能性があるため、データセットの反復回数が少ないほど良いことにも注意してください。

4

2 に答える 2

4

ここでの最善のアプローチは、デルタを記録するとともに、たとえば1000サンプルごとに、完全な状態データの定期的な「スナップショット」を取得することだと思います。元の値(別名デルタ)からのオフセットとしてデータを保存する場合、元の値から始めて完全なデータを再構築する以外に選択肢はありません。定期的なスナップショットを保存すると、実行する必要のある再構築の量が少なくなります。設計上のトレードオフは、ストレージ要件が低いが再構築時間が長いことと、ストレージ要件が高いが再構築時間が短いことです。

たとえば、MPEGは、各フレームを現在のフレームと前のフレームの差として保存します。通常、これによりMPEGが最初から表示されますが、この形式では定期的にフルフレームが保存されるため、デコーダーはファイルの先頭までバックトラックする必要がありません。

于 2009-07-09T12:59:28.913 に答える
1

Log(N)で時間で検索でき、許容できる更新の数を感じることができます...したがって、これが私の解決策です。

結果を返すために受け入れ可能な更新の数Nを選択します。これまでに言及したスケールを考えると、256が良いかもしれません。

Nレコードごとに、タイムスタンプを使用して、すべての状態のエントリを辞書にコミットします。

これで、速度に対する辞書のサイズというトレードオフがあります。N->\inftyは通常の検索です。N <-1が現在のソリューションです。他の場所では、必要なメモリは少なくなりますが、速度は遅くなります。

これで、実装は(時間Xの場合)次のようになります。サブサンプリングされたグローバルディクショナリをLog(n)で検索し、Xの前にタイムスタンプを付けます(タイムスタンプはYとして)。イベントリストのlog(n)検索をタイムスタンプYに記録し、N回未満の更新を実行します。

Nを2の累乗として選択すると、いくつかの優れたシフトトリックを実行して、切り捨てられた整数除算を適切かつ高速に実行することもできます。

于 2009-07-09T12:52:39.677 に答える