Cómo implementar un Digg-como algoritmo?

Question

Cómo implementar un sitio web con un sistema de recomendación similar a la de stackoverflow/digg/menéame?I. e., los usuarios enviar contenido y el sitio web debe calcular algún tipo de "calentura" de acuerdo a lo popular que es el elemento.El flujo es el siguiente:

• Los usuarios enviar contenido
• Otros usuarios ver y votar sobre el contenido (supone el 90% de los usuarios sólo a los puntos de vista de contenido y el 10% activamente votos hacia arriba o hacia abajo en el contenido)
• El nuevo contenido se presentó continuamente

¿Cómo implementar un algoritmo que calcula la "calentura" de un enviado elemento, de preferencia en tiempo real?Hay de mejores prácticas o patrones de diseño?

Quiero suponer que el algoritmo lleva a la siguiente consideración:

• Cuando un elemento se presentó
• Cuando cada voto
• Cuando el elemento se ve

E. g.un elemento que consigue un goteo constante de votos que se quedaría un poco "caliente", constantemente, mientras que un elemento que recibe una ráfaga de votos cuando se presentó por primera vez va a saltar a la parte superior de la "calentura"de la lista, pero luego se caen como los votos dejan de entrar.

(Estoy usando una base de datos MySQL+PHP, pero estoy interesado en general, patrones de diseño).

Answer 1

Usted podría utilizar algo similar a la Reddit algoritmo - el principio básico de que es calcular un valor para un post basado en el tiempo en que fue publicado y la puntuación.Lo genial de los Reddit algoritmo es que sólo se necesita calcular el valor cuando la puntuación de un post de los cambios.Cuando usted quiere mostrar su portada, que acaba de llegar a la cima n puestos de su base de datos basada en el puntaje.Como pasa el tiempo el puntaje de aumentar naturalmente, así que usted no tiene que hacer ningún procesamiento especial para quitar los elementos de la página principal.

Answer 2

En mi propio sitio, me asignar a cada entrada un número entero único de una monótona creciente de la serie (los nuevos puestos de obtener números más altos).Cada uno vote aumenta el número por uno, y cada voto disminuye por uno (usted puede ajustar estos valores, por supuesto).Luego, simplemente, ordenar por el número para mostrar el 'más caliente' entradas.

Answer 3

He desarrollado un sitio de marcadores sociales, Los Sitios Favoritos, y utiliza un complejo algoritm:

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 los puntos de uso.Para ganar puntos cada usuario debe agregar enlaces que conseguir los votos positivos.
2. A continuación, los usuarios pueden votar -3,-2,-1,1,2 o 3 votos para cada enlace.Como los votos son limitados, cada usuario votará únicamente en los enlaces que les gusta.
3. Para evitar que el usuario de voto únicamente en los enlaces para el mismo usuario, la creación de grupos de apoyo, los puntos de cada votación añade el enlace que depende de una racio entre el total de los votos y los votos a los enlaces de el propietario de la votación del enlace.Si siempre voto en el mismo a los usuarios enlaces, sus votos va a perder valor.
4. Votos a perder valor con el tiempo.
5. Nuevos enlaces de los usuarios que no tienen puntos (nuevos usuarios) tendrá una partida de 0 puntos.Nuevos enlaces de los usuarios de más edad se han de puntos en función de sus puntos.Que van desde +3 a -infinito.Los enlaces de los usuarios con puntos negativos negativas puntos de partida, los enlaces de los usuarios con puntos positivos que se han positivas puntos de partida.

Los usuarios podrán obtener puntos al azar cuando sus enlaces se votó.Los votos positivos dar puntos positivos, negativos votos de puntos negativos.

Answer 4

Paul Graham escribió un ensayo sobre lo que había aprendido en el desarrollo de Hacker News.El énfasis está más en las personas/interacciones que él estaba tratando de atraer a/crear que en el algoritmo de por sí, pero aún así vale la pena leer.Por ejemplo, él habla de los diferentes resultados cuando las historias de la burbuja de la parte inferior (HN) frente a la explosión de la parte superior (Digg) de la primera página.(Aunque por lo que he visto de HN, parece que las historias de explotar a la parte superior, también).

Él ofrece esta cita:

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

que a la luz de la supuesta algoritmo para la generación de la HN primera página:

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

donde

p = un artículo de puntos y

t = tiempo desde el envío del artículo

podría ser un buen punto de partida.

Answer 5

He implementado una versión SQL de Reddit del algoritmo de clasificación 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.Corre lo suficientemente rápido en nuestro sitio actual, pero estoy pensando en añadir un valor de clasificación de la columna y la actualización de la misma con el mismo gatillo como el *cached_votes_total* columna.Después de que la optimización, debe ser lo suficientemente rápido para la mayoría de cualquier tamaño sitio.