Comment implémenter un algorithme de type Digg?

Question

Comment implémenter un site Web avec un système de recommandation similaire à stackoverflow / digg / reddit? C'est-à-dire que les utilisateurs soumettent du contenu et que le site Web doit calculer une sorte de "hotness". selon la popularité de l'article. Le flux est le suivant:

• Les utilisateurs envoient du contenu
• D'autres utilisateurs visualisent et votent le contenu (supposons que 90% d'entre eux ne consultent que le contenu et 10% votent activement pour ou contre le contenu)
• Un nouveau contenu est soumis en permanence

Comment implémenter un algorithme qui calcule le "hotness" d'un élément soumis, de préférence en temps réel? Existe-t-il des meilleures pratiques ou des modèles de conception?

Je suppose que l'algorithme prend en compte les éléments suivants:

• Quand un élément a été soumis
• Quand chaque vote a été exprimé
• Lorsque l'élément a été consulté

E.g. un article qui obtient un filet constant de votes resterait un peu "chaud" constamment pendant qu’un élément qui reçoit une rafale de votes lorsqu’il est soumis pour la première fois saute en haut de la liste des "actualités" mais tombe ensuite lorsque les votes cessent d’entrer.

(J'utilise MySQL + PHP mais les modèles de conception généraux m'intéressent.)

Answer 1

Vous pouvez utiliser quelque chose de similaire à l’ algorithme Reddit - dont le principe de base est vous calculez une valeur pour une publication en fonction de l'heure à laquelle elle a été publiée et du score. Ce qui est bien avec l’algorithme Reddit, c’est que vous n'avez besoin de recalculer la valeur que lorsque le score d’une publication change. Lorsque vous souhaitez afficher votre page d'accueil, vous obtenez simplement les n premiers articles de votre base de données en fonction de ce score. Au fur et à mesure que le temps passe, les scores augmentent naturellement, vous n'avez donc pas à faire de traitement spécial pour supprimer des éléments de la page d'accueil.

Answer 2

Sur mon propre site, j'attribue à chaque entrée un entier unique issu d'une série de plus en plus monotone (les nouveaux messages reçoivent des nombres plus élevés). Chaque vote positif augmente le nombre d'un, et chaque vote négatif le diminue d'un (vous pouvez modifier ces valeurs, bien sûr). Ensuite, il vous suffit de trier par numéro pour afficher les entrées "les plus chaudes".

Answer 3

J'ai développé un site de bookmarking social, Sites Favoritos , et utilisé un algorithme complexe:

1. Tout d'abord, les votes sont finis, un utilisateur ne dispose que d'un nombre limité de votes et le nombre de votes dépend des points d'utilisateur. Pour gagner des points, chaque utilisateur doit ajouter des liens qui obtiennent des votes positifs.
2. Ensuite, les utilisateurs peuvent voter -3, -2, -1,1,2 ou 3 votes pour chaque lien. Les votes étant limités, chaque utilisateur votera uniquement sur les liens qu'il apprécie.
3. Pour empêcher les utilisateurs de voter uniquement sur les liens d'un même utilisateur, lors de la création de groupes de soutien, les points que chaque vote ajoute au lien dépendent du nombre total de votes et de votes pour les liens du propriétaire du lien voté. Si vous votez toujours sur les mêmes liens, vos votes perdront de la valeur.
4. Les votes perdent de la valeur avec le temps.
5. Les nouveaux liens des utilisateurs qui n'ont pas de points (nouveaux utilisateurs) auront un point de départ de 0 point. Les nouveaux liens d'anciens utilisateurs auront des points en fonction de leurs points. Allant de +3 à -infini. Les liens des utilisateurs avec des points négatifs auront des points de départ négatifs, les liens des utilisateurs avec des points positifs auront des points de départ positifs.

Les utilisateurs obtiendront des points au hasard lorsque leurs liens seront votés. Les votes positifs donnent des points positifs, les votes négatifs pour les points négatifs.

Answer 4

Paul Graham a écrit un essai sur ce qu’il a appris dans le développer Hacker News . L'accent est mis davantage sur les personnes / interactions qu'il essayait d'attirer / créer que sur l'algorithme en tant que tel, mais méritait néanmoins une lecture. Par exemple, il discute des différents résultats lorsque des histoires surgissent du bas (HN) au lieu d’exploser au sommet (Digg) de la première page. (Bien que, d'après ce que j'ai vu de HN, il semble que des histoires explosent également là-haut).

Il propose cette citation:

  

La clé de la performance est l’élégance, pas les bataillons de cas particuliers.

qui, à la lumière de la algorithme spécifié pour générer la page d'accueil HN:

  

(p - 1) / (t + 2) ^ 1,5

     

où

     

p = les points d'un article et

     

t = temps écoulé depuis la soumission de l'article

pourrait être un bon point de départ.

Answer 5

J'ai mis en œuvre une version SQL de l'algorithme de classement de Reddit pour un agrégateur de vidéos comme suit:

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 * est mis à jour par un déclencheur à chaque nouveau vote. Il fonctionne assez rapidement sur notre site actuel, mais je prévois d'ajouter une colonne de valeur de classement et de la mettre à jour avec le même déclencheur que la colonne * cached_votes_total *. Après cette optimisation, il devrait être assez rapide pour la plupart des sites de toutes tailles.