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

Question

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

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

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

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

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

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

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

Answer 1

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

Answer 2

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

Answer 3

Я разработал сайт социальных закладок, Sites Favoritos и использовали сложный АЛГОРИТМ:

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

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

Answer 4

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

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

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

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

(р - 1)/(T + 2)^1,5

где

р = ап пункты статьи и

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

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

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