근사 유사성 검색(Approximate similarity search)이라는 개념은 Exact similarity, 즉 기존의 정확한 값을 비교하는 접근 방법에서 발생하는 단점들을 극복하기 위해서 만들어졌다.
'유사성' 이란 개념은 애초에 그 단어 자체가 주관적인 성격을 띄고있다.
또 특정한 경우에는 Approximate한 결과 그 자체만으로도 유저의 니즈를 만족시킬 수 있다.
Approximate similarity search의 기본 전략에 대하여 알아보도록 하자.
1. Space Transformation
우리는 전 챕터에서 Space Transformation에 대해서 공부했다.변환된 공간에서의 거리는 기존 공간에서보다 작다. 따라서 이에따른 false hit의 가능성이 있다는 특징이 있다.Space transformation을 이용한 Approximate similarity search의 예시로 차원 축소 기술을 이용하는
KLT, DFT, DCT, DWT
VA-files
등등이 있다고 하는데,, 이 블로그에서는 다루지 않을 예정이다.
2. Reducing subsets of data to be examined
검사할 데이터들의 부분집합들을 감소시키는 방법이다.유망하지 않은(not-promising한) 데이터에는 애초에 접근을 하지 않는다는 메커니즘을 이용한다.따라서 false hit의 가능성 역시 존재한다.본 포스팅에서는 이 방법론에 대하여 자세히 다뤄보고자 한다.
검사할 데이터들의 양을 줄이는 방법은 크게 두 종류로 나눠볼 수 있는데,
1) Early termination strategies - 모든 데이터들의 검사가 끝나기 전에 알고리즘을 종료하는 방법
2) Relaxed branching strategies - 쿼리 영역과 중복되는 데이터 영역을 특정한 '가지치기 전략'을 이용하여 버리는 방법
이 있다.
Early Termination Strategies
기존의 'Exact Similarity Search' 알고리즘
기존의 알고리즘은 매 단계마다 발전이 있으면 계속 반복하면서 실행하다가,
더이상의 발전이 없을 때 비로소 종료하는 방식이다.
즉, 발전이 0을 향해 수렴해 가고 있는 상황에서도 중간에 멈추지 않고, 0이라는 수치에 도달할때 까지 실행한다는 의미다.
Approximate
similarity search 알고리즘
하지만 근사 유사성 검색 알고리즘은 위와 같이 남은 데이터들의 검색에서 얻을 수 있는 improve가 매우 낮다고 판단되면, 모든 데이터를 검사하지 않았어도 실행을 종료하는 것이다.
Relaxed Branching Strategies
기존의 Exact similarity 알고리즘은 쿼리 영역과 겹치는 모든 데이터 영역에 eccess 한 뒤 나머지를 버리는 방식이었다.
근사 유사성 검사 알고즘에서는,
쿼리와 겹치는 영역에서도 데이터 개체가 포함될 가능성이 낮은 경우라면, 그 영역을 버린다.
공간의 계층적 분해(hierarchical decomposition of the space)에 기반한 방법으로 접근할 때 효과적이라고 한다.
그림으로 된 예시를 보며 Approximate similarity search의 동작 방식을 이해해보자
set B1에는 o1, o2, o3 (갈색) 데이터들이 들어있고, B2에는 노란색, B3에는 초록색 데이터가 들어있는 상황이다.q를 중심으로부터 그려진 점선 원 안에 있는 데이터를 찾는 Range qurey 방식이다.
위 data structure의 접근 순서는 B1, B2, B3라 해보면,
제일 처음에 B1에 접근하여 o1을 report(찾고자 하는 데이터)할 것이다.
여기서 Searching을 종료하게 되면, o4와 o5(쿼리가 요구하는 데이터)는 miss하게 된다.
따라서 B2까지도 진행할 것이다.
B2를 탐색하며 o4와 o5를 report한다. 이렇게 되면 찾아야 하는 쿼리는 다 찾은 셈이다.물론 나머지 데이터 셋을 다 보지 않았기에 이 알고리즘은 데이터가 더 있는지, 없는지 알 수 없을 것이다.Approximate similarity searching가 하고자 하는 것이 위와 같은 상황에서 남은 데이터셋의 유망성을 판단하여,적절한 시기에 데이터 탐색을 종료하는 것이다.
여기까지 Approximate similarity searching의 등장 배경과, 종류, 그리고 간단한 예시를 살펴보았다.다음 포스팅에서는 Approximate similarity searching 알고리즘의 performance(성능)을 측정하는 지표들의 종류와, 측정 방법에 대해서 배워보도록 하자.
