많은 수의 항목에서 무작위로 반복되는 (반복되지 않는) 항목 선택

Question

관계형 데이터베이스에 저장된 텍스트 문서 모음이 많습니다 (300-500k). 각 문서는 하나 이상의 (최대 6 개) 범주에 속할 수 있습니다. StumbleUpon의 작동 방식과 같이 단일 항목이 반복되지 않도록 사용자가 특정 범주의 문서를 임의로 선택할 수 있어야합니다.

많은 사용자와 문서를 사용하여 느린 NOT 쿼리를 사용하여 구현할 수있는 방법이 실제로 보이지 않으므로이 용도로 일부 사용자 지정 데이터 구조를 구현해야 할 수도 있습니다. 아마도 이미 내 요구에 맞게 조정할 수있는 알고리즘을 설명하는 문서가있을 것입니다.

현재 나는 다음과 같은 접근 방식을 고려 중이 야 :

가이 범주에 속하는 문서의 ID를 각 범주의 연결리스트 인덱스를 만들고 데이터베이스 에서 모든 항목을 읽어보십시오. Shuffle it 특정 사용자가 보는 모든 항목을 포함하는 블룸 필터 만들기 반복자를 사용하여 색인을 탐색하고, 블룸 필터를 사용하여 항목을 임의로 선택하여 표시되지 않은 항목을 선택합니다.

Answer 1

해시 테이블 구현을 권장합니다. 이렇게하면 일정 시간 조회를 할 수 있습니다. linear probing이라는 기술을 구현할 수 있습니다. 연결된 목록은 검색 시간에 O(N)을 먹기 때문에 끔찍한 구현입니다.

관계형 데이터베이스 여야한다는 제약이 있다면 memcache (FB는 이것을 사용)와 같은 것을 사용하여 본질적으로 친구 문제의 친구를 유지할 수 있습니다.

Answer 2

임의의 순서로 데이터베이스에서 항목을 반환하는 방법은 this answer을 참조하십시오. 이제 사용자가 무작위 순서로 어디에서 (각 카테고리에 대해) 표시되고 Skip() 및 Take()가 표시되는지를 추적하여 다음 그룹의 레코드를 표시 할 수 있습니다. 사용자마다 임의의 XOR 값을 저장하여 각각 다른 시퀀스를 볼 수 있습니다.