今日のカウントで最も頻繁に発生するイベントN

Question

ウェブサイトのアナリティクスを構築し、今日最も人気のあるページをN個表示したいとします。アルゴリズムは、定数メモリと移動カウンタの2つの要件を満たす必要があります。

コンスタントメモリ

ページの十億があるかもしれません、我々はそれらのすべてのためのカウントを維持する必要はありません。このアルゴリズムでは、定数メモリを使用するスマートな確率カウンタを使用する必要があります。 Count–min sketchがありますが、すべての要素のカウントを推定しようとしているようですが、ここではすべての要素は気にしません。上位Nについてのみ考えます。

移動カウンタ上位Nページ

は毎日、今日のトップ2ページが/cats.htmlと/dogs.html可能性がありますが、明日、それは/pizza.htmlと/donuts.htmlなどの全く異なる ものになる可能性が異なっています。最も簡単なアプローチは毎日カウンターを再起動することですが、それは問題ありませんが、移動平均のようなスマートなアプローチがありますか？イベントのストリームの

例：

[ 
{ page: '/cats.html', time: 'today, 12:00' }, 
{ page: '/cats.html', time: 'today, 11:00' }, 
{ page: '/dogs.html', time: 'today, 10:00' }, 
{ page: '/dogs.html', time: 'today, 09:00' }, 
{ page: '/donuts.html', time: 'today, 08:00' }, 
{ page: '/donuts.html', time: 'yesterday, 20:00' }, 
{ page: '/cats.html', time: 'yesterday, 19:00' }, 
... 
] 

Answer 1

私の記憶が正しければ、あなたは一定のメモリで最頻値を得ることができますが、私はそれは、複数の値のために働くだろうとは思いません。

おおよその答えが十分であれば、HyperLogLogアルゴリズムを調べるとよいでしょう。ユニークな値の数をカウントするのとまったく同じ問題ではありませんが、そこで使用されているテクニックが問題を解決するのに役立つことがあります。

This questionも関連していますが、一定のメモリ制約はありません。