¿Cómo implementar un algoritmo tipo Digg?

Question

¿Cómo implementar un sitio web con un sistema de recomendación similar a stackoverflow/digg/reddit? Es decir, los usuarios envían contenido y el sitio web necesita calcular algún tipo de "calor" de acuerdo con la popularidad del artículo. El flujo es el siguiente:

• Los usuarios envían contenido
• Otros usuarios ver y votar sobre el contenido (a suponer el 90% de los usuarios solo vistas de contenido y el 10% de los votos activamente arriba o hacia abajo en el contenido)
• El nuevo contenido se envía continuamente

¿Cómo implemento un algoritmo que calcule el "picor" de un elemento enviado, preferiblemente en tiempo real? ¿Hay mejores prácticas o patrones de diseño?

quiero suponer que el algoritmo toma en consideración lo siguiente:

• Cuando se presentó un artículo
• Cuando fue echado cada voto
• Cuando se ve el elemento

P. ej un ítem que obtiene un chorrito constante de votos se mantendrá un tanto "caliente" constantemente mientras que un ítem que recibe un estallido de votos cuando se presente por primera vez saltará a la cima de la lista de "picor" pero luego caerá cuando los votos se detengan entrando.

(Estoy usando un PHP MySQL + pero estoy interesado en patrones generales de diseño).

Answer 1

Puede usar algo similar al Reddit algorithm, cuyo principio básico es calcular el valor de una publicación en función del momento en que se publicó y el puntaje. Lo bueno del algoritmo de Reddit es que solo necesita recalcular el valor cuando cambia el puntaje de una publicación. Cuando desee mostrar su página principal, solo obtendrá las primeras n publicaciones de su base de datos según ese puntaje. A medida que pasa el tiempo, los puntajes aumentarán de forma natural, por lo que no es necesario realizar ningún procesamiento especial para eliminar elementos de la página principal.

Answer 2

En mi propio sitio, asigno a cada entrada un número entero único de una serie monótonamente creciente (las publicaciones más nuevas obtienen números más altos). Cada voto aumenta el número en uno, y cada voto negativo lo disminuye en uno (puede modificar estos valores, por supuesto). Luego, simplemente ordena por el número para mostrar las entradas 'más calientes'.

Answer 3

que desarrolló un sitio de marcadores sociales, Sites Favoritos, y se utiliza un algoritmo complejo:

1. En primer lugar, los votos son finitos, un usuario sólo tienen un número limitado de votos, y el número de votos depende de la puntos de usuario Para ganar puntos, cada usuario debe agregar enlaces que obtengan votos positivos.
2. Luego, los usuarios pueden votar -3, -2, -1,1,2 o 3 votos para cada enlace. Como los votos son limitados, cada usuario votará solo aquellos enlaces que quiera.
3. Para evitar que el usuario vote solo en enlaces para el mismo usuario, creando grupos de apoyo, los puntos que cada voto agrega al enlace dependen de un racio entre el total de votos y votos a los enlaces del propietario del enlace votado. Si siempre vota en los mismos enlaces de usuarios, sus votos perderán valor.
4. Los votos pierden valor con el tiempo.
5. Los nuevos enlaces de usuarios que no tienen puntos (usuarios nuevos) tendrán 0 puntos iniciales. Los nuevos enlaces de usuarios mayores tendrán puntos dependiendo de sus puntos. Que van desde +3 hasta -infinito. Los enlaces de los usuarios con puntos negativos tendrán puntos de partida negativos, los enlaces de los usuarios con puntos positivos tendrán puntos de partida positivos.

Los usuarios obtendrán puntos aleatorios cuando se voten sus enlaces. Los votos positivos dan puntos positivos, votos negativos para puntos negativos.

Answer 4

Paul Graham escribió un ensayo sobre lo que aprendió en developing Hacker News. El énfasis está más en las personas/interacciones que estaba tratando de atraer/crear que en el algoritmo per se, pero aún así vale la pena leerlas. Por ejemplo, discute los diferentes resultados cuando las historias aparecen desde la parte inferior (HN) en lugar de explotar hasta la parte superior (Digg) de la página principal. (Aunque por lo que he visto de HN, parece que las historias también explotan hasta la cima).

él ofrece esta cita:

La clave del rendimiento es la elegancia, no batallones de casos especiales.

que la luz de la purported algorithm para la generación de la primera página HN:

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

donde

p = una puntos del artículo y

t = tiempo desde la presentación del artículo

podría ser un buen punto de partida.

Answer 5

he implementado una versión de SQL del algoritmo de clasificación de Reddit para un agregador de vídeo, así:

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 se actualiza por un gatillo cada vez que una nueva votación está echada. Se ejecuta lo suficientemente rápido en nuestro sitio actual, pero estoy planeando agregar una columna de valor de clasificación y actualizarla con el mismo activador que la columna * cached_votes_total *. Después de esa optimización, debe ser lo suficientemente rápido para la mayoría de los sitios de cualquier tamaño.