미터법 트리

메트릭 트리는 메트릭 공간의 데이터를 인덱싱하는 데 특화된 트리 데이터 구조다.미터법 트리는 삼각형 불평등과 같은 미터법 공간의 속성을 이용하여 데이터에 대한 접근을 보다 효율적으로 만든다.예를 들면 M-트리, vp-트리, 커버 트리, MVP 트리, BK-트리 등이 있다.^[1]

다차원 검색

데이터 집합을 검색하는 대부분의 알고리즘과 데이터 구조는 고전적인 이진 검색 알고리즘을 기반으로 하며, k-d 트리나 범위 트리 같은 일반화는 별도의 좌표 위에 바이너리 검색 알고리즘을 인터리빙하고 각 공간 좌표를 독립적인 검색 제약조건으로 취급하여 작동한다.These data structures are well-suited for range query problems asking for every point ${\displaystyle (x,y)}$ that satisfies ${\displaystyle {\mbox{min}}_{x}\leq x\leq {\mbox{max}}_{x}}$ and ${\displaystyle {\mbox{min}}_{y}\leq y\leq {\mbox{max}}_{y}}$.

이러한 다차원 검색 구조의 한계는 벡터로 취급할 수 있는 개체만을 검색하기 위해 정의된다는 것이다.그것들은 알고리즘이 단지 물체의 집합과 두 물체 사이의 거리나 유사성을 측정하기 위한 함수만 주어진 더 일반적인 경우에는 적용되지 않는다.예를 들어, 만약 누군가가 한 이미지가 다른 이미지와 얼마나 유사한지 나타내는 값을 반환하는 함수를 만든다면, 자연스러운 알고리즘 문제는 이미지의 데이터 집합을 취해서 주어진 쿼리 이미지와 함수에 따라 비슷한 값을 찾는 것이다.

미터법 데이터 구조

유사성 측정에 구조가 없는 경우 데이터 집합의 모든 이미지와 쿼리 이미지를 비교해야 하는 무차별적인 힘 검색이 최선의^{[citation needed]} 방법이다.그러나 유사함수가 삼각형 불평등을 만족시킨다면, 각 비교의 결과를 사용하여 검사할 후보군을 제거할 수 있다.

미터법에 관한 첫 번째 기사는 물론 공개 문헌에 발표된 "금속 나무"라는 용어의 첫 번째 용어는 1991년 제프리 울먼에 의해 발표되었다.^[2]다른 연구자들은 유사한 데이터 구조에 대해 독립적으로 연구하고 있었다.특히 피터 이아닐로스는 자신이 vantage point tree(VP-tree)라고 부르는 같은 방법을 독자적으로 발견했다고 주장했다.^[3]미터법 트리 데이터 구조에 대한 연구는 1990년대 후반에 꽃을 피웠고 구글 공동 창업자인 세르게이 브린이 매우 큰 데이터베이스에 사용하는지 여부를 검사하는 것을 포함했다.^[4]미터법 데이터 구조에 관한 최초의 교과서는 2006년에 출판되었다.^[1]

오픈 소스 구현

• Matlab: 미터법 트리는 에서 구현된다.metricTree미국 해군 연구소의 무료 추적기 구성요소 라이브러리의 일부인 클래스.^[5]

참조