다양한 행에있는 숫자 쌍을 효율적으로 검색하십시오.

Question

N 명의 개별 사용자가 있고이 사람들이 어디에 있는지, 정확히 정확하게 말하면이 레코드가 있다고 가정 해보십시오.

1,50,299 
1,2,3,4,5,50,287 
1,50,299 

예를

를 들어

그래서 당신은 '사람 1' '사람 50'세 번에 같은 장소에있는 것을 볼 수 있습니다. 여기서 M = 3은 분명히 3 라인이므로. 제 질문에이 줄 중 M 개가 주어지며 임계 값 (예 : 사람 A와 B가 임계 시간보다 더 같은 위치에 있었음)이 공동 발생을 반환하는 가장 효율적인 방법은 무엇이라고 생각하십니까?

지금까지 N by N 테이블을 만들고 각 행을 반복하면서 N 행이 M 행마다 발생할 때마다 테이블 (N, M)을 증가 시켰습니다. 분명히 이것은 끔찍한 접근이며 당신이 내포하는 방식에 따라 O (n^3)까지 0 (n^2)을 필요로합니다. 어떤 조언을 부탁드립니다!

Answer 1

표를 만들 필요가 없습니다. 귀하의 언어로 부르는 해시/사전/무엇이든 만들면됩니다. 그런 다음 의사 코드에서 : 당신이 크기 K의 크기의 M 세트가있는 경우

answer = [] 
for S in sets: 
    for (i, j) in pairs from S: 
     count[(i,j)]++ 
     if threshold == count[(i,j)]: 
      answer.append((i,j)) 

실행 시간이 O(M*K^2) 될 것입니다.

big-O를 변경하지 않고도 실제로 교차하는 데이터 세트의 목록을 count과 평행하게 유지할 수 있습니다.

또한 같은 알고리즘을 map-reduce를 사용하여 분산 된 방식으로 쉽게 구현할 수 있습니다. 카운트의 경우 (i, j) 키와 1 값을 방출하면됩니다. 당신이 그들을 줄이면됩니다. 실제로 세트 목록을 생성하는 것은 유사합니다.

Answer 2

사례에 대한 알려진 개념은 시장 바구니 분석입니다. 이 문맥에는 다른 알고리즘이 있습니다. 예를 들어 Apriori algorithm을 사용하면 특정 케이스에서 크기 2를 사용할 수 있습니다.

또한 이러한 경우에는 LSH 및 LSH를 사용하여 특정 지원 및 조건 (귀하의 경우 임계 값)을 사용하여 association rules을 최소 해시도.

Answer 3

속도를 높이기 위해 확률을 사용할 수 있습니다 (예 : 1/50 확률로 각 쌍만 검사하십시오. 그러면 속도가 50 배 향상됩니다. 그런 다음 M의 1/50까지 충분히 가까운 쌍을 확인하십시오.

쌍을 다시 확인하려면 전체 목록을 다시 검토하거나 영리한 행동을한다면 두 번 더 효율적으로 점검하십시오 당신은 역 색인 생성을합니다. 예 : 각 사람 행 인덱스를 64 비트 정수로 인코딩하면 이진 검색/병합 정렬 기법을 사용하여 비교할 64 비트 정수를 확인하고 비트 연산을 사용하여 64 비트 정수를 비교하여 일치 항목을 비교할 수 있습니다. 조회 할 다른 것들은 역 색인화, 2 진 색인화 된 범위 나무/펜윅 나무 일 수 있습니다.