Como implementar um algoritmo semelhante ao Digg?

Question

Como implementar um site com sistema de recomendação semelhante ao stackoverflow/digg/reddit?Ou seja, os usuários enviam conteúdo e o site precisa calcular algum tipo de “gostosura” de acordo com a popularidade do item.O fluxo é o seguinte:

• Os usuários enviam conteúdo
• Outros usuários visualizam e votam no conteúdo (suponha que 90% dos usuários apenas visualizam o conteúdo e 10% votam ativamente a favor ou contra o conteúdo)
• Novo conteúdo é enviado continuamente

Como faço para implementar um algoritmo que calcule o “gosto” de um item enviado, de preferência em tempo real?Existem práticas recomendadas ou padrões de design?

Eu diria que o algoritmo leva em consideração o seguinte:

• Quando um item foi enviado
• Quando cada voto foi dado
• Quando o item foi visualizado

Por exemplo.um item que recebe um fluxo constante de votos permaneceria um tanto "quente" constantemente, enquanto um item que recebe uma série de votos quando é enviado pela primeira vez saltará para o topo da lista de "gostoso", mas depois cairá quando os votos pararem entrando.

(Estou usando MySQL + PHP, mas estou interessado em padrões de design gerais).

Answer 1

Você poderia usar algo semelhante ao Algoritmo Reddit - cujo princípio básico é calcular um valor para uma postagem com base no horário em que foi postada e na pontuação.O que é interessante no algoritmo do Reddit é que você só precisa recalcular o valor quando a pontuação de uma postagem muda.Quando você deseja exibir sua página inicial, basta obter as n principais postagens de seu banco de dados com base nessa pontuação.Com o passar do tempo, as pontuações aumentarão naturalmente, então você não precisa fazer nenhum processamento especial para remover itens da primeira página.

Answer 2

No meu próprio site, atribuo a cada entrada um número inteiro exclusivo de uma série crescente monotonicamente (postagens mais recentes recebem números mais altos).Cada voto positivo aumenta o número em um, e cada voto negativo o diminui em um (você pode ajustar esses valores, é claro).Em seguida, basta classificar pelo número para exibir as entradas “mais populares”.

Answer 3

Desenvolvi um site de bookmarking social, Sites favoritos, e usou um algoritmo complexo:

1. Primeiro, os votos são finitos, um usuário tem apenas um número limitado de votos e o número de votos depende dos pontos do usuário.Para ganhar pontos cada usuário deve adicionar links que obtenham votos positivos.
2. Então, os usuários podem votar -3,-2,-1,1,2 ou 3 votos para cada link.Como os votos são limitados, cada usuário votará apenas nos links de sua preferência.
3. Para evitar que o usuário vote apenas em links do mesmo usuário, criando grupos de apoio, os pontos que cada voto agrega ao link dependem de uma razão entre o total de votos e os votos nos links do dono do link votado.Se você votar sempre nos links dos mesmos usuários, seus votos perderão valor.
4. Os votos perdem valor com o tempo.
5. Novos links de usuários que não possuem pontos (novos usuários) terão 0 pontos iniciais.Novos links de usuários mais antigos terão pontos dependendo de seus pontos.Variando de +3 a -infinito.Links de usuários com pontos negativos terão pontos de partida negativos, links de usuários com pontos positivos terão pontos de partida positivos.

Os usuários receberão pontos aleatórios quando seus links forem votados.Votos positivos dão pontos positivos, votos negativos dão pontos negativos.

Answer 4

Paul Graham escreveu um ensaio sobre o que aprendeu em desenvolvendo Notícias Hacker.A ênfase está mais nas pessoas/interações que ele estava tentando atrair/criar do que no algoritmo em si, mas ainda assim vale a pena ler.Por exemplo, ele discute os diferentes resultados quando as histórias surgem da parte inferior (HN) e explodem para o topo (Digg) da primeira página.(Embora pelo que vi de HN, pareça que as histórias explodem lá também).

Ele oferece esta citação:

A chave para o desempenho é a elegância, não batalhões de casos especiais.

que à luz do suposto algoritmo para gerar a primeira página do HN:

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

onde

p = pontos de um artigo e

t = tempo desde a submissão do artigo

pode ser um bom ponto de partida.

Answer 5

Implementei uma versão SQL do algoritmo de classificação do Reddit para um agregador de vídeo assim:

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* é atualizado por um gatilho sempre que um novo voto é lançado.Ele funciona rápido o suficiente em nosso site atual, mas estou planejando adicionar uma coluna de valor de classificação e atualizá-la com o mesmo gatilho da coluna *cached_votes_total*.Após essa otimização, ela deve ser rápida o suficiente para sites de qualquer tamanho.