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

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)를 모두 계..

이번 장에서는 쿼리 실행에 대한 원칙에 대해 배워보자. 쿼리에 답하기 위한 cost(비용)은 다음 두 가지에 영향을 받는다. 파티셔닝 원칙(Partitioning principle) 쿼리 실행 알고리즘(Query execution algorithm) 파티셔닝 원칙은 지난 블로그에서 다뤘으니, 이번에는 쿼리 실행 알고리즘에 대하여 다뤄보겠다. 알고리즘들을 보기 앞서, Hypothetical Index Organiztion에 대해 알아볼 필요가 있다. Hypothetical의 사전적 의미는 '가상의'라는 뜻으로, 직역하자면 '가상의 인덱스 구성'이라고 볼 수 있겠다. 일반적인 Array를 생각해보면, 각 배열에는 한개의 object가 존재한다. 하지만 위계질서(hierarchy)를 가진 entries로 노드..

이번 장에서는 기본적인 partitioning 원칙에 대해 다뤄보자. 거리 공간 M=(D,d)에 대하여 총 세 가지의 기본 분류 방법을 다뤄볼것이다. 1. Ball Partitioning 아주 기본적이고 간단한 방법이이다. 반지름 dm을 기준으로 안/ 밖에 속하는 object로 구분한 것이다. 좀 더 발전한 방법으로 Multi - way ball partitioning도 있다. 안과 밖의 두 집합으로 나누는 것이 아니라, 안/중간/밖 이렇게 세 부분으로 분류를 한다. 2. Generalized Hper-plane Partitioning Ball Partitioning이 원을 기준으로 구역이 나뉘었다면, Generalized hyper-plane Partitioning은 직선을 기준으로 로 구역이 나뉜다...

이번 장에서는 여러 유형의 쿼리에 대해서 다뤄보겠다. 1. Range query - 범위 쿼리 쿼리 q로부터 r반경에 있는 data들을 가져온다. 내 호텔로부터 2키로 반경 내에 있는 모든 박물관을 검색하는것을 예로 들 수 있다. R(q,r)에서 q : 내 호텔, r : 2km가 되겠다. 2. Nearest Neighbor Query The nearest neighbor query - 최근접 이웃 쿼리 쿼리로부터 가장 가까운 data를 '하나만' 검색한다. 내 호텔에서 가장 가까운 박물관을 검색하는 것을 예로 들 수 있다. K-nearest neighbor query - 근접 이웃 쿼리 쿼리로부터 가까운 순서대로 k개의 data를 검색한다. 내 호텔에서 가까운 순서대로 5개의 박물관을 검색하는 것을 예로..

Metric Space의 정의 거리 공간( metric space)은 두 점 사이의 거리가 정의된 공간이다. 거리의 정의에 따라 표준적인 위상상을 갖는다. Metric space M =(D,d)의 정의는 다음과 같다. M = (D,d) - Data domain D - Total (distance) function d: D * D -> [0,무한) 즉 데이터의 집합 D와, 데이터 간의 거리를 표현하는 function 'd'가 정의된 공간이라 할 수 있다. 이 거리공간은 다음과 같은 조건을 만족시켜야 한다. 위 조건들을 간단히 설명하자면, - 거리공간에서 서로 다른 두 점 사이의 거리는 음수가 될 수 없고(p1) - 임의의 점 x에서 y까지의 거리는 y에서 x까지의 거리와 같으며(p2) - 같은 두 점 사이..