밴티지 포인트 트리

Vantage-point tree

vantage-point 트리(또는 VP 트리)는 공간의 위치("vantage point")를 선택하고 데이터 포인트를 임계값보다 vantage point에 가까운 지점과 그렇지 않은 지점의 두 부분으로 분할하여 메트릭 공간에서 데이터를 분리하는 메트릭 트리다.이 절차를 재귀적으로 적용하여 데이터를 더 작고 작은 세트로 분할함으로써, 나무의 이웃이 공간의 이웃이 될 가능성이 높은 트리 데이터 구조를 만든다.[1]

하나의 일반화를 멀티밴티지 포인트 트리 또는 MVP 트리라고 부른다: 유사성 검색 쿼리를 위해 큰 메트릭 공간에서 객체를 인덱싱하기 위한 데이터 구조.각 수준을 분할하기 위해 둘 이상의 점을 사용한다.[2][3]

역사

피터 이아닐로스는 밴티지 포인트 나무가 자신(피터 이아닐로스)과 제프리 울만(Jeffrey Uhlmann)에 의해 독자적으로 발견되었다고 주장했다.[1]그러나 Uhlmann은 1991년 Yianilos 이전에 이 방법을 발표했다.[4]Uhlmann은 데이터 구조를 미터법 트리라고 불렀고, VP-트리라는 이름은 Yianilos에 의해 제안되었다.밴티지 포인트 트리는 닐슨 외 연구진이 브레그먼 분류를 이용해 비금속 공간으로 일반화했다.[5]

이 반복적인 분할 과정은 k-d 트리의 분할 과정과 유사하지만 직선형 분할 방식보다는 원형(또는 구형, 초자형 등)을 사용한다.2차원 유클리드 공간에서 이것은 일련의 원이 데이터를 분리하는 것으로 시각화할 수 있다.

vantage-point 트리는 비표준 메트릭 공간의 데이터를 메트릭 트리로 나누는 데 특히 유용하다.

vantage-point 트리 이해

vantage-point 트리가 데이터를 저장하는 방법은 원으로 나타낼 수 있다.[6]먼저 이 트리의 각 노드에 입력 지점과 반지름이 포함되어 있음을 이해하십시오.주어진 노드의 모든 왼쪽 자녀는 원 안에 있는 지점이고, 주어진 노드의 모든 오른쪽 자녀는 원 밖에 있다.나무 자체는 무엇이 저장되고 있는지에 대한 다른 정보를 알 필요가 없다.미터법 공간의 속성을 만족시키는 거리 기능만 있으면 된다.[6]

vantage-point 트리를 검색하는 중

vantage-point 트리는 점 x의 가장 가까운 이웃을 찾는 데 사용될 수 있다.검색 알고리즘은 재귀적이다.주어진 단계에서 우리는 vantage point v와 임계값 거리 t를 가진 트리의 노드를 가지고 작업하고 있다.관심 지점 x는 vantage 지점 v에서 어느 정도 거리가 될 것이다. d 거리가 t보다 작으면 알고리즘을 재귀적으로 사용하여 임계값 t보다 vantage 지점에 더 가까운 지점을 포함하는 노드의 하위 트리를 검색한다. 그렇지 않으면 vantage 지점보다 더 먼 지점을 포함하는 노드의 하위 트리에 반복된다.임계값 t보다 안티지점.알고리즘의 재귀적 사용이 x에 대한 거리가 t - d 미만인 인접 지점 n을 발견하면 이 노드의 다른 하위 트리를 검색하지 않을 수 없으며, 발견된 노드 n은 반환된다.그렇지 않으면 다른 하위 트리도 재귀적으로 검색할 필요가 있다.

유사한 접근방식은 점 x의 가장 가까운 이웃을 찾는 데 효과적이다.재귀에서 다른 하위 트리는 지금까지 발견된 가장 가까운 이웃의 k³(< k)만이 t - d보다 작은 거리를 가질 때마다 지점 x의 가장 가까운 k - k³를 검색한다.

밴티지 포인트 트리의 장점

  1. 지수를 구축하기 전에 도메인의 다차원 점을 유추하는 대신 거리에 따라 지수를 직접 구축한다.[6]이렇게 하면 사전 처리 단계를 피할 수 있다.
  2. vantage-point 트리를 업데이트하는 것은 FastMap 접근법에 비해 상대적으로 쉽다.FastMap의 경우, 데이터를 삽입하거나 삭제한 후 FastMap이 자체적으로 다시 검색해야 하는 시기가 올 것이다.그것은 너무 많은 시간을 소모하고 언제 재검색이 시작될지 알 수 없다.[6]
  3. 거리 기반 방법은 유연하다."정확한 수의 치수의 형상 벡터로 표현되는 객체를 지수화할 수 있다."[6]

복잡성

Vantage-Point 트리를 만드는 데 소요되는 시간 비용은 대략 O(n log n)이다.각 원소에 대해 트리는 위치를 찾기 위해 로그 n 레벨에 의해 하강한다.그러나 k가 트리 노드당 vantage 지점의 수인 상수 요인 k가 있다.[3]

Vantage-Point 트리를 검색하여 가장 가까운 이웃 하나를 찾는 데 걸리는 시간은 O(log n)이다.각각 k 거리 계산을 포함하는 로그 n 레벨이 있으며, 여기서 k는 트리의 해당 위치에 있는 vantage 점(요소)의 수입니다.

Vantage-Point 트리에서 범위를 검색하는 데 소요되는 시간 비용은 가장 중요한 속성이 될 수 있으며, 사용되는 알고리즘과 파라미터의 세부 사항에 따라 크게 달라질 수 있다.브린의 논문은[3] 거리 계산 수로 측정된 비용을 조사하기 위해 다양한 매개변수를 가진 여러 가지 유리한 지점 알고리즘으로 실험한 결과를 제시한다.

Vantage-Point 트리의 공간 비용은 대략 n이다.각 요소는 저장되며, 각 잎이 아닌 노드의 트리 요소마다 하위 노드에 대한 포인터가 필요하다.한 가지 구현 선택에 대한 자세한 내용은 Brin을 참조하십시오.각 노드의 요소 수에 대한 매개변수가 하나의 요인으로 작용한다.)

일부 메트릭 공간 도구는 쌍으로 된 거리 값의 행렬을 필요로 하며 비용은 O(n2)이지만 Vantage-Point 트리에서는 필요하지 않다.

참조

  1. ^ a b Yianilos (1993). Data structures and algorithms for nearest neighbor search in general metric spaces (PDF). Fourth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics Philadelphia, PA, USA. pp. 311–321. pny93. Retrieved 2008-08-22.
  2. ^ Bozkaya, Tolga; Ozsoyoglu, Meral (September 1999). "Indexing Large Metric Spaces for Similarity Search Queries". ACM Trans. Database Syst. 24 (3): 361–404. doi:10.1145/328939.328959. ISSN 0362-5915.
  3. ^ a b c Brin, Sergey (Sep 1995). "Near Neighbor Search in Large Metric Spaces". VLDB '95 Proceedings of the 21th International Conference on Very Large Data Bases. Zurich, Switzerland: Morgan Kaufmann Publishers Inc.: 574–584.
  4. ^ Uhlmann, Jeffrey (1991). "Satisfying General Proximity/Similarity Queries with Metric Trees". Information Processing Letters. 40 (4): 175–179. doi:10.1016/0020-0190(91)90074-r.
  5. ^ Nielsen, Frank (2009). "Bregman vantage point trees for efficient nearest Neighbor Queries". Proceedings of Multimedia and Exp (ICME). IEEE. pp. 878–881.
  6. ^ a b c d e Fu, Ada Wai-chee; Polly Mei-shuen Chan; Yin-Ling Cheung; Yiu Sang Moon (2000). "Dynamic vp-tree indexing for n-nearest neighbor search given pair-wise distances". The VLDB Journal — The International Journal on Very Large Data Bases. Springer-Verlag New York, Inc. Secaucus, NJ, USA. pp. 154–173. vp. Retrieved 2012-10-02.

외부 링크