상위 10 개 경로 축소 맵 축소

Question

경로 탐색 그래프가 필요한 프로젝트에서 작업 중입니다.

문제 설명 : http://bl.ocks.org/mbostock/4063570 국지적 인 차이는 사이트 탐색이 될 것입니다 : 프로젝트 컨텍스트를 제공하기는 샘플 UI가 유사 할 것으로 예상된다. 내 문제는 백엔드 데이터를 다루는 데있다. 사용자 경로 A-> B-> C-> D-> E 를 들어

내가 미리 계산 데이터 형식은 다음과 같습니다

Origin:Start:End:Level 
A A B L1 
A B C L2 
A C D L3 
A D E L4 

을 지금, 100 년대와 같은 기록의 수백만 있다고 가정 근원, 나는 그들을 그룹화 할 수 있고, 크기를 집계하고 크기를 기준으로 정렬하고 10을 차지할 수 있습니다. 그래서 각 원점, 시작 및 레벨에 대해 각각 10 개의 레코드가 있어야합니다. 4 레벨의 그래프의 경우 그래프의 주어진 시작 노드에 대해 10 .. 10^2 .. 10^3 .. 10^4를 갖습니다.

실제 문제 : 정렬 후 상위 10 위는 불필요한 L3과 L4를 모두 제거 할 수 없습니다. 주어진 원점에 대해 L1의 끝은 L2의 시작이어야하며, L2의 끝은 L3의 시작이어야합니다. 이런 이유 때문에 많은 L2 레코드가 L1 레코드에 속하지 않은 많은 레코드를 가지고 있으며 레벨 증가로 증가합니다. 그림 : 내가 뭘하려

A A B L1 
A B C L2 
A F G L2 <-- this comes in top 10 after aggregation, but start is not the end of L1 (B in this case) 

: 정렬 및 10을 공격 태도를 보여준 후, 나는 자기가 1 씩 각 레벨 1에서 기록의 수백만에 가입 할 내가 10 레벨이있다. 그것은 계산 상으로 정말로 비쌉니다.

내가 찾고있는 것 : 일반적이고 저렴한 Map-reduce 솔루션. 나는 끓는 맥락에서 그것을 얻을 수 있다면 더 좋다.여기

Answer 1

나는 해결책을 가지고,하지만 난 당신을 위해 소송입니다 확실하지 않다 :

AAB L1을 : 나는 당신이 좋아하는 모든-필요하지 않은 기록을 빼앗아되어 수행 할 작업을 가정

ABC L2

AFG-L2 일부 불필요 R 려 그래서

(L2 내지 F에 대한 아무런 개시가 없기 때문에, 빼앗아 맞지) 우리는 기록이 필요한지 여부를 알아야합니다. 나는 다음과 같이 해결책을 제시한다 :

먼저 메모리 데이터 구조 DB (Redis 또는 Hazelcast와 유사)가 있어야한다. 첫 번째 MapReduce에서는 메모리 데이터 구조 DB에 데이터를 삽입하기 만하면됩니다. 우리가 여기에 삽입하는지도 데이터입니다 (키가 시작이다 : L1 B : 같은 수준 L5, 값이 끝이있는 목록입니다) :

A :지도 어쩌면이 같은

L1 -> B

A : L2-> 우리는 InMemoryDB을 가지고 있기 때문에 우리가 필요한 모든 기록을 알 최초의 맵리 듀스 후 CG

; 두 번째 MapReduce는 적합하지 않은 레코드를 가져옵니다.

우리는 다음과 같은 기록을 만들 수 있습니다. 매퍼에서 우리는 InMemoryDB의지도에서 getList와 같이 A : L1 키를 사용하여 쿼리합니다 (L1을 사용합니다 (L2에서 양식을 시작했기 때문에 이것을 사용합니다). 만약 F가 필요하다면, 그렇지 않다면 그렇지 않다.