Digg のようなアルゴリズムを実装するにはどうすればよいですか?

Question

stackoverflow/digg/reddit に似たレコメンデーション システムを備えた Web サイトを実装するにはどうすればよいですか?つまり、ユーザーがコンテンツを送信すると、Web サイトはそのアイテムの人気度に応じて、ある種の「人気度」を計算する必要があります。流れは以下の通りです。

• ユーザーがコンテンツを送信する
• 他のユーザーはコンテンツを表示して投票します (ユーザーの 90% はコンテンツのみを表示し、10% はコンテンツに対して積極的に賛成または反対の投票を行うと仮定します)。
• 新しいコンテンツが継続的に投稿されます

送信されたアイテムの「ホットさ」を、できればリアルタイムで計算するアルゴリズムを実装するにはどうすればよいですか?ベストプラクティスや設計パターンはありますか?

このアルゴリズムでは次のことが考慮されていると思います。

• アイテムが送信されたとき
• 各投票が行われたとき
• アイテムが閲覧されたとき

例えば。継続的に少しずつ投票を獲得する項目は、常にある程度の「人気」を維持しますが、最初に送信されたときに一気に投票を獲得した項目は、「人気」リストのトップに躍り出ますが、投票が止まると順位が下がります。入ってきます。

(私は MySQL+PHP を使用していますが、一般的なデザイン パターンに興味があります)。

Answer 1

次のようなものを使用できます Redditアルゴリズム - 基本原則は、投稿の時刻とスコアに基づいて投稿の値を計算することです。Reddit アルゴリズムの優れた点は、投稿のスコアが変化した場合にのみ値を再計算する必要があることです。トップページを表示したいときは、そのスコアに基づいてデータベースから上位 n 件の投稿を取得するだけです。時間の経過とともにスコアは自然に増加するため、トップページからアイテムを削除するために特別な処理を行う必要はありません。

Answer 2

私自身のサイトでは、単調増加系列からの一意の整数を各エントリに割り当てます (新しい投稿には大きな番号が付きます)。賛成票を投じるたびに数値が 1 ずつ増え、反対票を投じるたびに数値が 1 ずつ減ります (もちろん、これらの値を調整することもできます)。次に、数字で並べ替えるだけで、「最も人気のある」エントリが表示されます。

Answer 3

ソーシャルブックマークサイトを開発しましたが、 サイトのお気に入り, 、複雑なアルゴリズムを使用しました。

1. 第一に、投票は有限であり、ユーザーが持つ投票数には制限があり、投票数はユーザー ポイントに依存します。ポイントを獲得するには、各ユーザーは肯定的な投票を得るリンクを追加する必要があります。
2. その後、ユーザーはリンクごとに -3、-2、-1、1、2、または 3 票を投票できます。投票には制限があるため、各ユーザーは気に入ったリンクにのみ投票します。
3. ユーザーが同じユーザーのリンクのみに投票できないようにサポート グループを作成し、各投票によってリンクに追加されるポイントは、総投票数と投票されたリンクの所有者のリンクへの投票との比率に応じて決まります。常に同じユーザーのリンクに投票すると、投票の価値が失われます。
4. 投票は時間の経過とともに価値を失います。
5. ポイントを持たないユーザー (新規ユーザー) からの新しいリンクは、0 ポイントから開始されます。古いユーザーからの新しいリンクには、ポイントに応じてポイントが付与されます。+3 から - 無限までの範囲です。マイナスポイントを持つユーザーからのリンクはマイナスの出発点を持ち、プラスポイントを持つユーザーからのリンクはプラスの出発点を持ちます。

ユーザーはリンクが投票されるとランダムなポイントを獲得します。肯定的な投票はプラスのポイントを与え、否定的な投票はマイナスのポイントを与えます。

Answer 4

ポール・グレアムは、大学で学んだことについてエッセイを書きました。 ハッカーニュースの開発中. 。アルゴリズムそのものよりも、彼が引き付けたり作ろうとした人々やインタラクションに重点が置かれていますが、それでも一読の価値は十分にあります。たとえば、彼は、記事がトップページの一番下から湧き出てくる場合（HN）と、トップページに爆発的に広がっていく場合（Digg）の場合の異なる結果について説明しています。（HNを見た限りでは、そこでもストーリーが爆発的に盛り上がっているように見えますが）。

彼はこんな名言を残しています。

パフォーマンスの鍵となるのは優雅さであり、特別なケースの大隊ではありません。

を踏まえると 主張されているアルゴリズム HN フロント ページを生成する場合:

(p - 1) / (t + 2)^1.5

どこ

p = 記事のポイント、

t = 記事の投稿からの時間

良い出発点になるかもしれません。

Answer 5

次のように、ビデオ アグリゲーター用に Reddit のランキング アルゴリズムの SQL バージョンを実装しました。

SELECT id, title
FROM videos
ORDER BY 
    LOG10(ABS(cached_votes_total) + 1) * SIGN(cached_votes_total)   
    + (UNIX_TIMESTAMP(created_at) / 300000) DESC
LIMIT 50

*cached_votes_total* は、新しい投票が投じられるたびにトリガーによって更新されます。現在のサイトでは十分に高速に実行されますが、ランキング値列を追加し、*cached_votes_total* 列と同じトリガーで更新することを計画しています。この最適化後は、ほとんどの規模のサイトで十分な速度が得られるはずです。