R * 트리 분할 평면 선택

Question

this paper을 기반으로하는 R * 트리의 구현 작업을하고 있습니다. 분할 축 알고리즘을 선택하는 것에 대해 몇 가지 질문이 있습니다.

R * -tree는 좋은 스플릿을 찾기 위해 followmg 메서드를 사용합니다. 각 축을 따라, 엔트리는 먼저 더 낮은 값으로 정렬 된 다음, 직사각형의 상위 값에 의해 정렬됩니다.

사각형의 위/아래 값은 무엇을 의미합니까?

각 분포에 대해 양호도 값이 결정됩니다. 이러한 선량 값에 따라 항목의 최종 분포가 결정됩니다. 서로 다른 세 가지 가치와 다양한 조합으로 사용하는 다양한 접근 방법을 실험적으로 테스트합니다.

(I) 영역 값 영역 [BB (제 1 군)] + 영역 [BB (초 기)]

(II) 마진 값의 마진 [BB (제 1 군)] + 마진 [BB (두 번째 군)]

(III) 중첩 값 영역 [BB (제 1 군) + (BB) (제 기)]

여기에서 BB는 직사각형

세트의 바운딩 박스를 나타내고 어떤 margin-value을 의미합니까? 이 값을 계산하려면 어떻게해야합니까?

Answer 1

내가 알 수있는 한 "직사각형의 하한값/상한값"은 해당 축을 따라 직사각형의 최소값과 최대 값입니다.

링크 된 기사의 p323에 따르면, "여백은 직사각형의 가장자리 길이의 합계입니다."

Answer 2

사각형은 대개 각 차원에서 min + max의 쌍으로 표시됩니다. 따라서 "위"와 "위"값은 최소값과 최대 값입니다.

여백은 둘레입니다. 그 이유는 많은 상황에서 사각형이 직사각형의 선호 유형이기 때문입니다. 예를 들어, 유클리드 (또는 맨해튼, 거의 모든 Lp 표준) 가장 가까운 이웃 검색을 할 때. 그 이유는 그것들이 어떤 사람들에게는 "편파적"이지 않기 때문입니다.

Ang et Tan의 "선형"분할과 같은 다른 분할 전략은 이것을 무시하고 매우 길고 조각을 생성하는 경향이 있습니다.

https://en.wikipedia.org/wiki/File:Zipcodes-Germany-AngTanSplit.svg

이들의 R이 * - 트리 피하려고 분할의 종류입니다 : 위키 백과는이에 대한 예제가 있습니다. 대부분의 쿼리는 이러한 슬라이스를 교차하므로 매우 적은 이득을 얻습니다.

R * -tree는 여러 가지 휴리스틱 및 타이 브레이커를 사용합니다. 게다가 그것은 두 단계의 결정을 내립니다 : 먼저 그것은 분할에 사용할 축을 선택합니다. 축이 결정되면 실제로 다른 논리를 사용하여이 축을 따라 분할을 선택합니다.