잘지내자, 우리 잘지내자, 우리

4. Double-Pivot Distance Constraint 이전장에서 다룬 pivot-pivot distance constraint에서는, 하나의 피벗만 사용한 'Ball partitioning'에서 사용 가능한 constraint였다. Generalized hyper-plane에 적용하기 위해서는, 2개의 피벗을 사용해야한다. 피벗 두개를 사용하여 만약 q와 o가 다른 subspace에 존재한다 가정해보자. lower bound는 (d(q,p1) - d(q,p2))/2 5. Pivot Filtering - object-pivot constraint의 확장으로, 더 많은 pivot을 사용한다. - pruning을 위해 삼각부등식을 사용한다. - 모든 object들과 pivot p 사이의 거리를 알고..

이번 장에서는 '거리 계산'을 피하는 방법론에 대하여 다뤄보겠다. 개인적으로 이해하는데 꽤나 고생했던 부분이다. 거리를 측정한다는 것은 비싼 연산과정을 필요로 하기 때문에, 거리 측정에 대한 회수를 제한한다면 similarity queries를 처리하는데 필요한 속도를 향상시킬 수 있게 된다. 이러한 과정에 대한 전략을 'Pruning strategies(가지치기 전략)'이라 부르는데, 오늘은 이 가지치기 전략의 종류와 그 내용을 알아보자 1. Object-Pivot Constraint 다음과 같은 data structure이 있다고 하자. Range query R(q,r)을 구해야하고, 현재 가장 왼쪽 leaf를 방문하고있다다 해보자. 평소대로라면 d(q,o4).d(q,o6),d(q,o10)를 모두 계..