행의 세트에서 부모 요소를 찾는 방법

Question

나는 같은 데이터의 집합을 가지고있다. 하이 레벨 SQL 함수 또는 HIVE/PIG (간단한 추측)에서의 쉬운 방법이 가능합니까?

Answer 1

당신이하려는 것은 모든 노드의 그래프에서 연결된 각 하위 그래프를 찾는 것입니다. 먼저 그래프를 작성한 다음 연결된 하위 그래프를 찾는 모든 노드를 살펴보고 해결할 수 있습니다.

"큰"그래프를 만들려면 각 노드는 문자이고 두 글자는 같은 세트에 속해 있으면 함께 연결됩니다.

그런 다음 각 문자로 이동하여이 문자로 시작하는 그래프를 탐색하고 표시되는 각 문자를 제거하십시오. 검색 알고리즘을 다시 시작하는 시간은 사용자가 설정 한 횟수입니다.

복잡성을 감안할 때 그래프 구성은 가지고있는 세트 수와 다른 문자 수에 따라 다릅니다. 그래프 검색의 경우 문자 수와 연결 수가 선형입니다. 물론 당신의 세트가 주어진 방식과 사용하는 데이터 구조에 따라 최적화를 할 수 있습니다.

자세한 내용은 wikipedia.