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

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

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

Как реализовать алгоритм, который вычисляет "горячность" отправленного элемента, предпочтительно в режиме реального времени? Есть ли лучшие практики или шаблоны проектирования?

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

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

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

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

Ответы

Ответ 1

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

Ответ 2

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

Ответ 3

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

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

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

Ответ 4

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

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

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

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

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

где

p = точки товара и

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

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

Ответ 5

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