Digg와 유사한 알고리즘을 구현하는 방법은 무엇입니까?

Question

stackoverflow/digg/reddit와 유사한 추천 시스템을 사용하여 웹사이트를 구현하는 방법은 무엇입니까?즉, 사용자가 콘텐츠를 제출하면 웹사이트는 항목이 얼마나 인기 있는지에 따라 일종의 "인기"를 계산해야 합니다.흐름은 다음과 같습니다.

• 사용자가 콘텐츠를 제출함
• 다른 사용자가 콘텐츠를 보고 투표합니다(90%의 사용자가 콘텐츠를 보기만 하고 10%는 적극적으로 콘텐츠에 대해 찬성 또는 반대 투표를 한다고 가정).
• 새로운 콘텐츠가 지속적으로 제출됩니다.

제출된 항목의 "인기"를 가급적 실시간으로 계산하는 알고리즘을 어떻게 구현합니까?모범 사례나 디자인 패턴이 있나요?

알고리즘은 다음 사항을 고려한다고 가정합니다.

• 항목이 제출되었을 때
• 각 투표가 이루어졌을 때
• 해당 항목을 본 시점

예:지속적으로 조금씩 투표를 받는 항목은 지속적으로 "인기" 상태를 유지하는 반면, 처음 제출되었을 때 폭발적인 투표를 받은 항목은 "인기" 목록의 맨 위로 올라갔다가 투표가 중단되면 아래로 떨어집니다. 온다.

(저는 MySQL+PHP를 사용하고 있지만 일반적인 디자인 패턴에 관심이 있습니다.)

Answer 1

다음과 비슷한 것을 사용할 수 있습니다. 레딧 알고리즘 - 기본 원칙은 게시물이 게시된 시간과 점수를 기준으로 게시물의 가치를 계산하는 것입니다.Reddit 알고리즘의 장점은 게시물 점수가 변경될 때만 값을 다시 계산하면 된다는 것입니다.첫 페이지를 표시하려면 해당 점수를 기준으로 데이터베이스에서 상위 n개의 게시물을 가져오면 됩니다.시간이 지남에 따라 점수는 자연스럽게 증가하므로 첫 페이지에서 항목을 제거하기 위해 특별한 처리를 할 필요가 없습니다.

Answer 2

내 사이트에서는 단조롭게 증가하는 시리즈에서 각 항목에 고유한 정수를 할당합니다(최신 게시물이 더 높은 숫자를 얻음).찬성 투표를 할 때마다 숫자가 1씩 증가하고 반대 투표를 할 때마다 숫자가 하나씩 감소합니다(물론 이 값은 조정할 수 있습니다).그런 다음 숫자별로 정렬하면 '가장 인기 있는' 항목이 표시됩니다.

Answer 3

소셜 북마킹 사이트를 개발했는데, 사이트 즐겨찾기, 복잡한 알고리즘을 사용했습니다.

1. 첫째, 투표는 유한하고, 사용자는 제한된 수의 투표만 할 수 있으며, 투표 수는 사용자 포인트에 따라 달라집니다.포인트를 얻으려면 각 사용자가 긍정적인 투표를 받는 링크를 추가해야 합니다.
2. 그런 다음 사용자는 각 링크에 대해 -3,-2,-1,1,2 또는 3표를 투표할 수 있습니다.투표가 제한되어 있으므로 각 사용자는 자신이 좋아하는 링크에만 투표하게 됩니다.
3. 사용자가 동일한 사용자의 링크에만 투표하는 것을 방지하기 위해 지원 그룹을 만들 때 각 투표가 링크에 추가하는 포인트는 총 투표와 투표한 링크 소유자의 링크에 대한 투표 간의 비율에 따라 달라집니다.항상 동일한 사용자 링크에 투표하면 투표의 가치가 떨어집니다.
4. 투표는 시간이 지날수록 가치를 잃습니다.
5. 포인트가 없는 사용자(신규 사용자)의 새 링크는 시작 포인트가 0입니다.이전 사용자의 새 링크에는 해당 포인트에 따라 포인트가 부여됩니다.+3부터 -무한까지입니다.부정적인 점을 가진 사용자의 링크는 부정적인 시작점을 가지며, 긍정적인 점을 가진 사용자의 링크는 긍정적인 시작점을 갖습니다.

사용자는 링크가 투표되면 무작위 포인트를 받게 됩니다.긍정적인 투표는 긍정적인 점수를 주고, 부정적인 투표는 부정적인 점수를 줍니다.

Answer 4

Paul Graham은 자신이 배운 내용에 대한 에세이를 썼습니다. 해커 뉴스 개발.알고리즘 자체보다는 그가 끌어들이거나 창조하려고 했던 사람/상호작용에 더 중점을 두고 있지만 여전히 읽을 가치가 있습니다.예를 들어, 그는 기사가 첫 페이지의 맨 아래(HN)에서 솟아오르는 것과 첫 페이지의 맨 위로(Digg) 폭발할 때의 다양한 결과에 대해 논의합니다.(내가 HN에서 본 바에 따르면 그곳에서도 이야기가 최고 수준으로 폭발하는 것처럼 보입니다.)

그는 다음과 같은 인용문을 제시합니다.

성능의 핵심은 특별한 경우의 대대적인 것이 아니라 우아함입니다.

어느 점에 비추어 볼 때 알려진 알고리즘 HN 첫 페이지를 생성하려면:

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

어디

p = 기사의 요점 및

t = 기사 제출 후의 시간

좋은 출발점이 될 수 있습니다.

Answer 5

다음과 같이 비디오 수집기에 대한 Reddit 순위 알고리즘의 SQL 버전을 구현했습니다.

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* 열과 동일한 트리거로 업데이트할 계획입니다.최적화 후에는 대부분의 모든 규모의 사이트에서 충분히 빨라질 것입니다.