Principles of Similarity Query Execution

 

이번 장에서는 쿼리 실행에 대한 원칙에 대해 배워보자.

 

쿼리에 답하기 위한 cost(비용)은 다음 두 가지에 영향을 받는다.

• 파티셔닝 원칙(Partitioning principle)
• 쿼리 실행 알고리즘(Query execution algorithm)

 

파티셔닝 원칙은 지난 블로그에서 다뤘으니, 이번에는 쿼리 실행 알고리즘에 대하여 다뤄보겠다.

알고리즘들을 보기 앞서, Hypothetical Index Organiztion에 대해 알아볼 필요가 있다.

 

Hypothetical의 사전적 의미는 '가상의'라는 뜻으로, 직역하자면 '가상의 인덱스 구성'이라고 볼 수 있겠다.

일반적인 Array를 생각해보면, 각 배열에는 한개의 object가 존재한다.

하지만 위계질서(hierarchy)를 가진 entries로 노드를 구성할 수도 있다.

즉 N = (G, R(g))로 한 인덱스를 채워넣을 수 도 있다는 의미이다.

 

만약 위의 자료처럼 Bounding region R(G)를 Ball region으로 채택한다면,

다음과 같은 Index Organization이 생성될 수 있다.

즉 인덱스 안에 바로 Object가 존재할 수 도 있지만, Object의 region 그 자체가 인덱스 한 칸을 차지할 수 도 있는 것이다.

 

자 이제 쿼리의 검색 알고리즘으로 넘어가보자.

 

---

 

1. Range Search Algorithm

Q = R(q,r)이라는 쿼리가 주어졌다.

이렇게 보면 복잡해 보이지만, 실제로는 매우 단순한 알고리즘이다.

 

루트 노드부터 탐색을 하고, 현재 노드의 모든 원소들에 대해 탐색을 진행한다. 모든 노드에 대해서 다음과 같은 과정을 반복하는데,

• 만약의 노드의 원소가 기본단위의 element라면
  • q(쿼리)와의 거리를 계산하여 Range(범위)안에 속한다면 Ouput에 넣는다
• 노드의 원소가 또 다른 구조체의 주소라면
  • 주소를 따라가 주소에 들어있는 원소에 대하여 위 과정을 재귀적으로 반복한다.

 

• B1이 루트이기 때문에 B1의 있는 원소를 대상으로 순회를 시작한다.
• o1-o4는 모두 기본 원소이기 때문에 그 자체로 검사를 한다.
• B3은 구조체의 주소이기 때문에 따라들어간다
  • B3의 원소들에 대해서도 재귀적으로 과정을 반복한다.
  • o5-o7은 기본 원소이게 때문에 자체로 검사를 한다.
• B2도 구조체의 주소이므로 따라 들어간다.
  • B2의 원소들에 대해서 재귀적으로 과정을 반복한다.
  • o8, o9에 대해 검사한다. -> 조건에 해당하므로 reponse에 저장한다.

 

2. Nearest Neighbor Search Algorithm

 

to be continue..