분산 트리 검색

Distributed tree search

분산 트리 검색(DTS) 알고리즘은 효율적이고 분산된 방식으로 값을 검색하기 위한 알고리즘 클래스입니다.이 솔루션의 목적은 트리와 같은 데이터 구조에서 값을 검색하는 데 소요되는 시간을 최소화하기 위해 여러 분기를 병렬로 따라 작업하고 각 분기의 결과를 하나의 공통 솔루션으로 병합하여 트리를 통해 반복하는 것입니다.

원본 논문은 캘리포니아 대학 컴퓨터 과학부의 크리스 퍼거슨과 리처드 E. 코프에 의해 1988년에 작성되었습니다.그들은 이 더 넓은 범위의 알고리즘을 개발하기 위해 여러 개의 다른 체스 인공지능을 사용했습니다.

개요

분산 트리 검색 알고리즘(Korf-Ferguson 알고리즘이라고도 함)은 다음과 같은 문제를 해결하기 위해 만들어졌습니다: "비균일한 분기 인자와 깊이를 가진 트리가 주어지면, 가능한 한 빨리 임의의 수의 프로세서와 병렬로 검색하십시오."

이 알고리즘의 최상위 부분은 일반적이며 특정 기존 유형의 트리 검색을 사용하지 않지만 모든 유형의 비분산 트리 검색에 맞게 쉽게 전문화할 수 있습니다.

DTS는 각각 노드와 프로세서 세트가 연결된 여러 프로세스를 사용하여 해당 노드 아래의 하위 트리를 검색하는 것을 목표로 합니다.그런 다음 각 프로세스는 여러 조정된 하위 프로세스로 분할되며, 각 프로세스에서 사용할 수 있는 프로세서 수에 따라 트리를 검색하는 최적의 방법이 발견될 때까지 다시 재귀적으로 분할됩니다.프로세스가 완료되면 DTS는 특히 불규칙한 트리에서 우수한 로드 밸런싱을 통해 효율을 최대로 유지하기 위해 프로세서를 다른 프로세스에 동적으로 재할당합니다.

프로세스가 검색을 마치면 모든 다른 하위 응답이 병합되고 전체 문제가 [1]해결될 때까지 결과 신호를 부모 프로세스로 재귀적으로 보내고 병합합니다.

적용들

DTS는 검색할 데이터 구조가 트리이고 알고리즘이 하나 이상의 계산 단위를 사용할 수 있다는 두 가지 주요 조건에서만 적용됩니다(단, 하나만 있는 경우 분산된 것으로 간주할 수는 없음).

DTS를 일상적으로 사용하는 주요 예 중 하나는 네트워크 라우팅입니다.인터넷은 IP 주소의 트리로 볼 수 있으며, 라우팅 프로토콜과 유사하게 우체국이 실제 환경에서 작동하는 방식이 될 수 있습니다.현재 43억 개 이상의 IP 주소가 있기 때문에, 사회는 데이터가 목적지에 도달하는 데 걸리는 시간에 크게 의존합니다.이와 같이 IP 라우팅은 작업을 여러 개의 하위 단위로 나누고 각 하위 단위는 서로 다른 스케일의 계산 기능을 가지며 서로의 결과를 사용하여 매우 효율적으로 경로를 찾습니다.이것은 엔터테인먼트에서 국가 [2]안보에 이르기까지 전 세계 인구의 43% 이상에 영향을 미치는 DTS의 한 예입니다.

대안

DTS는 현재 가장 널리 사용되는 알고리즘 중 하나이지만, DTS의 많은 응용 프로그램에는 더 많은 연구가 진행되면 잠재적으로 더 효율적이고 리소스를 덜 필요로 하는 솔루션으로 발전할 수 있는 대안이 있습니다.

더 논란이 되는 예 중 하나는 빅 데이터 처리입니다.Google 검색 엔진, Facebook, YouTube와 같은 응용 프로그램에서 검색은 적절한 창 안에서 대기 시간을 유지하도록 최적화되어야 합니다.이는 DTS를 일반적으로 사용함으로써 달성될 수 있지만, 다른 알고리즘이 제자리에서 사용되거나(예: SQL 데이터베이스의 데이터 해싱), 또는 함께 사용됩니다(Facebook의 Haystack 알고리즘은 병렬 트리 검색, 데이터 해싱 및 메모리 순서 지정/[3]정렬).

DTS의 가장 중요한 한계 중 하나는 입력으로 트리가 필요하다는 것입니다.트리는 그래프로 알려진 데이터 구조의 하위 인스턴스이며, 이는 모든 그래프를 트리로 변환할 수 있음을 의미합니다.현재 Korf-Ferguson의 알고리즘보다 트리를 통해 검색하는 더 나은 방법은 없지만, 각 작업은 서로 다른 특수성을 가지고 있으며 대부분의 경우 트리 검색을 통해 문제를 표현하고 해결하는 것보다 더 효율적인 데이터 구조가 존재할 것입니다.그래서 동일한 처리 능력을 가진 동일한 구조의 그래프 검색보다 더 빠를 수 없는 주기를 가진 트리 구조의 사례가 존재합니다.

논란

Korf-Ferguson의 DTS 알고리즘은 매우 완전하지만 단순한 것으로 인식되기 때문에 논란이 거의 없습니다.그것은 학생들이 분산 문제 해결의 기본과 핵심 개념을 발견하기 위한 디딤돌로 매우 자주 사용됩니다.

이 알고리즘 개념에 대한 가장 중요한 도전은 Kröll B의 기사인 《균형 잡힌 분산 검색 트리가 존재하지 않는다》였는데, 이는 알고리즘의 정확성이나 현재 효율성을 공격하지 않고, (예를 들어, 사전에 입력 트리의 균형을 유지하는 것과 같은) DTS 자체를 얼마나 많이 개선했든 간에,최적의 해상도 [4]시간에 도달할 수 없습니다.이것은 새로운 관점을 엽니다. DTS를 완료하는 데 너무 많은 리소스가 사용되어 효율성이 높은 새로운 알고리즘이 연구 및 개발되지 않도록 차단합니까?DTS(디지털 스로틀 및 시프트)의 또 다른 한계는 솔루션의 분할, 조정 및 병합이 아무리 효율적이라고 해도 항상 재료 수 또는 프로세서와 그 처리 능력에 의해 제한된다는 점입니다.

참고 항목

  • Colbrook A., Brewer E., Dellarocas C., Weihl W., "메시지 전달 아키텍처에서 검색 트리를 위한 알고리즘" (1996)
  • Colbrook A., Smythe C., 병렬 분산 메모리 아키텍처에서 검색 트리의 효율적인 구현"(1990)
  • Bayer R., McCreight E., 대형 주문 지수의 조직 및 유지. 액타 인포매티카 1 (1972)
  • Comer D., 유비쿼터스 B-트리 (1979)

레퍼런스

  1. ^ KORF Richard E., FERGUSON Chris (1988). "Distributed Tree Search and its Application to Alpha-Beta Pruning" (PDF). AAAI. University of California, Los Angeles. Archived from the original (PDF) on 2016-05-31.
  2. ^ "What is IP Routing ?". MetaSwitch. MetaSwitch Networks. 2016.
  3. ^ Vajgel, Peter (April 30, 2009). "Needle in a Haystack : Efficient Storage of Billions of Photos". Facebook. Facebook (company).
  4. ^ Kröll, Brigitte; Widmayer, Peter (1995-08-16). Akl, Selim G.; Dehne, Frank; Sack, Jörg-Rüdiger; Santoro, Nicola (eds.). Balanced distributed search trees do not exist. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 50–61. doi:10.1007/3-540-60220-8_50. hdl:20.500.11850/68782. ISBN 9783540602200.