Как реализовать Digg-подобный алгоритм?

Как реализовать веб-сайт с системой рекомендаций, подобной stackoverflow/digg/reddit? То есть пользователи отправляют контент, и веб-сайт должен вычислить своего рода «горячость» в зависимости от того, насколько популярен этот элемент. Поток выглядит следующим образом:

  • Пользователи отправляют контент
  • Другие пользователи просматривают контент и голосуют за него (предполагается, что 90% пользователей только просматривают контент, а 10% активно голосуют за или против контента)
  • Постоянно добавляется новый контент

Как мне реализовать алгоритм, который вычисляет «горячость» представленного элемента, предпочтительно в режиме реального времени? Существуют ли какие-либо передовые методы или шаблоны проектирования?

Я бы предположил, что алгоритм учитывает следующее:

  • Когда товар был отправлен
  • Когда каждый голос был подан
  • Когда товар был просмотрен

Например. элемент, который получает постоянный поток голосов, будет постоянно оставаться несколько «горячим», в то время как элемент, который получает всплеск голосов при первой отправке, подпрыгнет на вершину списка «горячих», но затем упадет вниз, когда голоса перестанут приходит в.

(Я использую MySQL + PHP, но меня интересуют общие шаблоны проектирования).


sql algorithm recommendation-engine digg
person Niklas    schedule 16.09.2008    source источник
comment
связанный вопрос, который документирует формулу, которую мы используем: meta.stackexchange.com/questions/11602/   -  person Jeff Atwood    schedule 31.01.2010

Ответы (5)


arrow_upward
6
arrow_downward

Вы можете использовать что-то похожее на алгоритм Reddit, основной принцип которого заключается в том, что вы вычисляете ценность поста в зависимости от времени его публикации и оценки. Что хорошо в алгоритме Reddit, так это то, что вам нужно пересчитывать значение только при изменении оценки публикации. Когда вы хотите отобразить свою первую страницу, вы просто получаете n лучших сообщений из своей базы данных на основе этого балла. Со временем баллы будут естественным образом увеличиваться, поэтому вам не нужно выполнять какую-либо специальную обработку, чтобы удалить элементы с первой страницы.

person Kyle Cronin    schedule 16.09.2008
comment
Копатель никогда не будет использовать алгоритм Reddit. Всегда. - person Tamás Szelei; 31.01.2010

arrow_upward
4
arrow_downward

На моем собственном сайте я присваиваю каждой записи уникальное целое число из монотонно возрастающей серии (более новые сообщения получают более высокие номера). Каждый голос «за» увеличивает число на единицу, а каждый голос «против» уменьшает его на единицу (конечно, вы можете настроить эти значения). Затем просто отсортируйте по номеру, чтобы отобразить самые популярные записи.

person Nick Johnson    schedule 19.09.2008

arrow_upward
1
arrow_downward

Я разработал сайт социальных закладок Sites Favoritos и использовал сложный алгоритм:

  1. Во-первых, количество голосов ограничено, у пользователя есть только ограниченное количество голосов, а количество голосов зависит от очков пользователя. Чтобы заработать баллы, каждый пользователь должен добавлять ссылки, которые получают положительные голоса.
  2. Затем пользователи могут проголосовать -3, -2, -1,1,2 или 3 голоса за каждую ссылку. Поскольку количество голосов ограничено, каждый пользователь будет голосовать только за те ссылки, которые ему нравятся.
  3. Чтобы запретить пользователю голосовать только за ссылки для одного и того же пользователя, создавая группы поддержки, баллы, которые каждый голос добавляет к ссылке, зависят от соотношения между общим количеством голосов и голосов по отношению к ссылкам владельца проголосовавшей ссылки. Если вы всегда будете голосовать по ссылкам одних и тех же пользователей, ваши голоса потеряют ценность.
  4. Голоса со временем теряют ценность.
  5. Новые ссылки от пользователей, у которых нет баллов (новые пользователи), будут иметь начальное значение 0 баллов. Новые ссылки от старых пользователей будут иметь баллы в зависимости от их баллов. В диапазоне от +3 до -бесконечно. Ссылки от пользователей с отрицательными баллами будут иметь отрицательные начальные точки, ссылки от пользователей с положительными очками будут иметь положительные начальные точки.

Пользователи будут получать случайные баллы, когда за их ссылки будут голосовать. Положительные голоса дают положительные баллы, отрицательные голоса дают отрицательные баллы.

person Community    schedule 19.09.2008

arrow_upward
1
arrow_downward

Пол Грэм написал эссе о том, чему он научился при разработке Hacker News. Акцент делается больше на людях/взаимодействиях, которых он пытался привлечь/создать, чем на алгоритме как таковом, но все же его стоит прочитать. Например, он обсуждает разные результаты, когда истории всплывают снизу (HN) и взрываются вверх (Digg) на первой полосе. (Хотя из того, что я видел о HN, похоже, что и там истории взрываются).

Он предлагает эту цитату:

Ключом к производительности является элегантность, а не батальоны особых случаев.

что в свете предполагаемого алгоритма для создания главной страницы HN:

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

куда

p = баллы за статью и

t = время с момента подачи статьи

может быть хорошей отправной точкой.

person Rich Apodaca    schedule 11.04.2010

arrow_upward
1
arrow_downward

Я реализовал SQL-версию алгоритма ранжирования Reddit для агрегатора видео следующим образом:

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* обновляется триггером всякий раз, когда подается новый голос. Он работает достаточно быстро на нашем текущем сайте, но я планирую добавить столбец значений рейтинга и обновить его с помощью того же триггера, что и столбец *cached_votes_total*. После этой оптимизации он должен быть достаточно быстрым для большинства сайтов любого размера.

person Chris Broski    schedule 31.10.2012