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

영역 분할을 하는데 사용하는 기존의 접근 방식에 대해 조사해보았다. 첫 번째로, Ball Partitioning에 대한 방법들을 알아보자. Burkhard-Keller Tree (BKT) BKT라고도 불린다. 특징으로는 다음 4가지가 있다. - Applicable to discrete distance functions only : 이산적인 거리만 적용할 수 있다. 연속적인 거리는 안된다는 말. - Recursively divides a given dataset X : 재귀적으로 주어진 데이터셋 X를 분할한다. 나머지 두 특징은 특수기호가 포함되어있어 이미지로 대체하였다. 위의 두 특징을 해석하자면, 임의의 점 pj로 부터 같은 거리에 위치한 점들을 Xi로 묶어 pj의 서브트리에 저장한다는 얘기이다. BK..

트리의 품질 측정 예전에 배운 가상 index에 대해 생각해보면, 우리는 같은 데이터셋을 가지고도 서로 다른 트리를 생성할 수 있다. 아래의 그림과 같이, 똑같은 데이터셋을 다른 tree structure로 구성할 수 있는 것이다. 우리는 이렇게 빌드할 수 있는 서로 다른 트리에 대하여, 어떤 트리가 더 품질이 좋은지 평가할 수 있다. 첫 번째 트리는 영역간에 겹치는 부분이 없고, 트리의 리프 노드의 점유율이 높다. 따라서 더 컴팩트한 트리라 할 수 있다. 반면에 두 번째 트리는 영역간의 중복이 많고, 트리의 리프 노드의 점유율이 좋지 않다. 따라서 첫 번째 트리에 비해 컴팩트하지 않다. 우리는 첫 번째 트리가 더 양질의 트리로 취급힌다. 이런 식으로, 트리의 품질을 측정하는 측도에 대해 알아보자. 가장..

Proximity of Metric Ball Regions 주어진 두 ball region 에 대하여, proximity는 다음과 같이 정의된다. 실제 사용되는 데이터셋에서, distance distribution이 특정한 object에 의존하지 않는다. 또한 실제 데이터셋은 높은 homogeneity의 인덱스를 가진다. (homogeneity에 대해서는 직전 포스팅에서 다뤘다) 따라서 overall proximity를 유용하게 사용할수 있고, 그 수식은 아래와 같다. 즉 임의의 거리에 있는 두 점을 찍고, 그 두 점에게 각각의 반지름 r1과 r2를 지정해 주었을 때, 두 영역이 얼마나 겹치느냐를 나타내는 것이다. 데이터셋이 높은 homogeneity를 가지기 때문에, 어떤 두 점이 주어지든 그 사이의 ..

데이터 셋이 가지는 통계적인 특징들은 데이터베이스의 성능 최적화의 기초가 된다. 이러한 통계적 특징들을 이용하여 Cost models를 만든다던가, Access structure tuning등을 할 수 있다. 이러한 통계적 정보들로는, 데이터베이스의 레코드에 대한 빈도 값 히스토그램이나 데이터의 분산 등이 있을 수 있다. 하지만,, 이러한 통계적 특성들을 일반적인 metric space에서는 사용하지 못한다. Metric space의 특성은 이 카테고리의 첫 번째 글에 설명해두었다. Metric space에서는 오로지 distance(거리)라는 변수에 의존해야하며,좌표계를 사용 할 수 없다. 하지만 통계를 사용하면 얻을 수 있는 이점들은 뽑아먹고 싶다.그래서 오늘은 metric space를 이용한 유사도..

Measures of Performance 이번 포스팅에서는 근사 유사성 검사의 성능을 측정하는 방법에 대해 알아볼 것이다. 성능을 평가할 때 고려해야할 사항으로는, - 효율성의 증가 정도 - 근사 결과의 정확도 위 두가지를 생각 할 수 있다. 일반적으로, 위의 두 사항은 서로 절충관계에 있다. 높은 효율성을 가진 알고리즘은 그만큼 정확도가 낮아진다. Good approximate search 알고리즘이란, 높은 효울성을 가지면서 높은 정확도 또한 보장하는 알고리즘이다. Measures of Performance: Improvement in Efficiency 성능을 측정하는 지표중 하나로, 효율성의 향상도가 있다. 효율성의 향상도는 - 쿼리의 정확한 실행 비용과 대략적인 실행 비용 사이의 비율로 표시된..

근사 유사성 검색(Approximate similarity search)이라는 개념은 Exact similarity, 즉 기존의 정확한 값을 비교하는 접근 방법에서 발생하는 단점들을 극복하기 위해서 만들어졌다. '유사성' 이란 개념은 애초에 그 단어 자체가 주관적인 성격을 띄고있다. 또 특정한 경우에는 Approximate한 결과 그 자체만으로도 유저의 니즈를 만족시킬 수 있다. Approximate similarity search의 기본 전략에 대하여 알아보도록 하자. 1. Space Transformation 우리는 전 챕터에서 Space Transformation에 대해서 공부했다.변환된 공간에서의 거리는 기존 공간에서보다 작다. 따라서 이에따른 false hit의 가능성이 있다는 특징이 있다.Sp..

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