Come implementare un algoritmo simile a Digg?

Question

Come implementare un sito web con un sistema di consigli simile a stackoverflow/digg/reddit?Cioè, gli utenti inviano contenuti e il sito web deve calcolare una sorta di "calore" in base alla popolarità dell'articolo.Il flusso è il seguente:

• Gli utenti inviano contenuti
• Altri utenti visualizzano e votano il contenuto (si presuppone che il 90% degli utenti visualizzi solo il contenuto e che il 10% voti attivamente a favore o contro il contenuto)
• Nuovi contenuti vengono continuamente inviati

Come posso implementare un algoritmo che calcoli il "piccante" di un articolo inviato, preferibilmente in tempo reale?Esistono best practice o modelli di progettazione?

Suppongo che l'algoritmo prenda in considerazione quanto segue:

• Quando è stato inviato un elemento
• Quando è stato espresso ciascun voto
• Quando l'elemento è stato visualizzato

Per esempio.un elemento che riceve un flusso costante di voti rimarrà costantemente "caldo" mentre un elemento che riceve un'esplosione di voti quando viene inviato per la prima volta salterà in cima alla lista "caldo" ma poi cadrà quando i voti si interrompono in arrivo.

(Sto utilizzando MySQL+PHP ma sono interessato ai modelli di progettazione generali).

Answer 1

Potresti usare qualcosa di simile a Algoritmo di Reddit - il cui principio di base è calcolare un valore per un post in base all'ora in cui è stato pubblicato e al punteggio.La cosa bella dell'algoritmo Reddit è che devi ricalcolare il valore solo quando cambia il punteggio di un post.Quando desideri visualizzare la tua prima pagina, ottieni semplicemente i primi n post dal tuo database in base a quel punteggio.Con il passare del tempo i punteggi aumenteranno naturalmente, quindi non è necessario eseguire alcuna elaborazione speciale per rimuovere elementi dalla prima pagina.

Answer 2

Sul mio sito, assegno a ciascuna voce un numero intero univoco da una serie monotonicamente crescente (i post più recenti ottengono numeri più alti).Ogni voto positivo aumenta il numero di uno e ogni voto negativo lo diminuisce di uno (ovviamente puoi modificare questi valori).Quindi, ordina semplicemente in base al numero per visualizzare le voci "più interessanti".

Answer 3

Ho sviluppato un sito di social bookmarking, Siti preferiti, e ha utilizzato un algoritmo complesso:

1. Innanzitutto, i voti sono limitati, un utente ha solo un numero limitato di voti e il numero di voti dipende dai punti dell'utente.Per guadagnare punti ogni utente deve aggiungere link che ottengono voti positivi.
2. Quindi, gli utenti possono votare -3,-2,-1,1,2 o 3 voti per ciascun collegamento.Poiché i voti sono limitati, ogni utente voterà solo sui link che gli piacciono.
3. Per evitare che l'utente voti solo sui link per lo stesso utente, creando gruppi di supporto, i punti che ogni voto aggiunge al link dipendono da un rapporto tra voti totali e voti ai link del proprietario del link votato.Se voti sempre sui link degli stessi utenti, i tuoi voti perderanno valore.
4. I voti perdono valore con il tempo.
5. I nuovi collegamenti da utenti che non hanno punti (nuovi utenti) avranno un valore iniziale di 0 punti.I nuovi collegamenti degli utenti più vecchi avranno punti in base ai loro punti.Da +3 a -infinito.I collegamenti di utenti con punti negativi avranno punti di partenza negativi, i collegamenti di utenti con punti positivi avranno punti di partenza positivi.

Gli utenti riceveranno punti casuali quando i loro collegamenti verranno votati.I voti positivi danno punti positivi, i voti negativi danno punti negativi.

Answer 4

Paul Graham ha scritto un saggio su ciò che ha imparato sviluppando Hacker News.L'enfasi è più sulle persone/interazioni che stava cercando di attrarre/creare che sull'algoritmo in sé, ma vale comunque la pena leggerlo.Ad esempio, discute i diversi risultati quando le storie emergono dal basso (HN) rispetto all'esplosione in alto (Digg) della prima pagina.(Anche se da quello che ho visto di HN, sembra che anche lì le storie esplodano verso l'alto).

Offre questa citazione:

La chiave della performance è l'eleganza, non i battaglioni di casi speciali.

che alla luce del presunto algoritmo per generare la prima pagina HN:

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

Dove

p = punti di un articolo e

t = tempo dalla presentazione dell'articolo

potrebbe essere un buon punto di partenza.

Answer 5

Ho implementato una versione SQL dell'algoritmo di classificazione di Reddit per un aggregatore di video in questo modo:

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* viene aggiornato da un trigger ogni volta che viene espresso un nuovo voto.Funziona abbastanza velocemente sul nostro sito attuale, ma sto pensando di aggiungere una colonna del valore di classifica e di aggiornarla con lo stesso trigger della colonna *cached_votes_total*.Dopo tale ottimizzazione, dovrebbe essere abbastanza veloce per la maggior parte dei siti di qualsiasi dimensione.