Tree Quality Measures

트리의 품질 측정

 

예전에 배운 가상 index에 대해 생각해보면, 우리는 같은 데이터셋을 가지고도 서로 다른 트리를 생성할 수 있다.

아래의 그림과 같이, 똑같은 데이터셋을 다른 tree structure로 구성할 수 있는 것이다.

우리는 이렇게 빌드할 수 있는 서로 다른 트리에 대하여, 어떤 트리가 더 품질이 좋은지 평가할 수 있다.

 

첫 번째 트리는 영역간에 겹치는 부분이 없고, 트리의 리프 노드의 점유율이 높다.

따라서 더 컴팩트한 트리라 할 수 있다.

반면에 두 번째 트리는 영역간의 중복이 많고, 트리의 리프 노드의 점유율이 좋지 않다.

따라서 첫 번째 트리에 비해 컴팩트하지 않다.

우리는 첫 번째 트리가 더 양질의 트리로 취급힌다.

 

이런 식으로, 트리의 품질을 측정하는 측도에 대해 알아보자.

 

가장 대표적인 측정 방법으로는 Fat Factor이 있다.

---

Fat Factor

 

트리 품질은 거리 공간에서의 겹치는 부분이 얼마나 많은지에 따라 달라진다.

즉 중복되는 영역이 얼마나 많은지 알아내는 것이 품질 측정의 기본이 된다.

위는 중복되는 영역을 측정하는 공식이다.

 

하지만 Fat Factor은 위와 같이 중복 영역을 계산하는 방법과는 다르다.

 

Fat Factor은 모든 데이터베이스에 대한 정확한 쿼리에 응답하는 데 필요한 총 노드 액세스 수를 계산한다.

영역 R1과 R2의 중복영역에 o가 포함된 경우, R(o,0)에 대해 해당하는 두 노드에 액세스된다.

 

Metric 트리 T가 n개의 object를 가지고있고 높이는 h이며, m>= 1의 노드를 가지고 있다 하면,

다음과 같은 공식이 Fat Factor을 측정하는 공식이다.

Ic는 n개의 정확한 쿼리 매치 검사를 하면서 엑세스된 총 node의 개수이다. 즉 nh 과 nm 사이의 값을 가진다.

 

가장 이상적인 트리는 트리의 level당 한 노드만에 접근하면 되는 트리이다.이 경우 Ic = nh로(한 레벨당 하나의 노드만 접근하므로)fat(T) = 0이 된다.

 

최악의 트리는 모든 노드에 접근하는 트리로,이 경우 Ic = nm이 된다. 수식에 대입하여 계산하면,fat(T) = 1이 된다.

 

예시를 보며 직접 계산해보자.

 

아래는 5섯개의 object를 각각 두 개의 트리로 구성한 것이다.

 

두 트리 모두, n = 5, m = 3, h = 2이다.

 

첫 번째 트리의 경우 중복되는 경우가 생긴다.

모든 리프 노드의 깊이가 2이기 때문에, 접근하는데 10의 비용이 들고,

추가적으로 o1의 자식 노드에서 o3를 찾는 소요가 있기 때문에 1이 늘어 11의 소요가 든다.

Ic = 11을 대입하여 Fat Factor을 계산해보면, (11 - 10) / 5 * 1 / 1 = 0.2이다.

 

두 번째 노드에는 중복의 경우가 없다.

따라서 Ic의 값은 10으로 계산된다.

마찬가지로 Fat Factor의 값을 계산해보면, 0이 된다.

 

이와 같은 방법으로 어떤 트리의 퀄리티가 더 좋은지 수치를 통해 판단 할 수 있다.

 

---

Relative Fat Factor

Fat Factor에서는 트리 안에 있는 노드의 개수는 고려하지 않았다.

따라서 낮은 fat-factor을 같는 큰 트리가, 조금 더 큰 fat-factor을 갖는 작은 트리보다 성능이 더 좋은 경우가 발생할 수 있다.

 

Relative Fat Factor은 최소 노드 수를 초과하는 트리에 패널티를 적용하는 방식으로 위의 문제를 해결한다.

Relative Fat Factor의 계산 값은 아래와 같이 정의된다.

c를 노드의 용량이라고 두면,

h_min과 m_min은 다음과 같이 구할 수 있다.

 

이제 아래 트리를 보며 트리의 성능을 판단해보자.

 

n = 9, c = 3, h_min = 2, m_min = 4이다.

 

두 트리 모두 fat(T)의 값은 0이지만, rfat(T)의 값은 오른쪽의 트리가 0.5의값을 가짐으로써, 

왼쪽 트리의 성능이 더 우수하다는 것을 알 수있다.

 

 

---

오늘 배운 내용을 정리해보자.

 

트리의 품질을 판단하는 지표에는 두 가지가 있다.

 Absolute fat-factor

- 0<= fat(T) <= 1

- 꽉 채워지지 않은 노드를 따로 고려하지 않는다.

- 같은 레벨의 노드에서 중복된 영역이 측정된다.

 

 Relative fat-factor

- rfat(T) >= 0

- 작은 트리일수록 성능이 좋게 나온다.

- 중복된 부분과, 노드가 얼마나 꽉 차있느냐 두 가지 모두를 고려한다.