Similarity queries

 

이번 장에서는 여러 유형의 쿼리에 대해서 다뤄보겠다.

 

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개의 박물관을 검색하는 것을 예로 들 수 있다.

 

---

 

3. Reverse Nearest Neigbor query

kRNN은 다소 난해하게 느껴질 수 있다.

간단하게 말하자면,

k-NN(q)는 q로부터 가까운 k개의 data를찾는것이라면,

kRNN(q)는 가까운 k개의 data중 q를 가지는 data를 구하는 것이다.

이 그림을 예로 들어 생각해보자.

위 그림은 2-RNN의 예이다.

각 object(data)마다 2번째로 가까운 object를 기준으로 원을 그린 것이다.

따라서, 이 원 안에 q가 들어가있다면 해당 object는 쿼리가 검색하고자 하는 object에 해당된다.

O4를 보면, q를 1번째로 가까운 object로 가지고, O5를 2번째로 가까운 object로 가진다.

즉 knn(O4)에 q가 포함되므로, 2-RNN(q)에는 O4가 포함된다.

마찬가지로 O5, O6도 2-RNN(q)의 원소가 된다.

여기서 집고 넘어가야할 사실은,

KNN(q)의 결과는 k개이지만, RKNN(q)의 결과는 k개가 아닐 수도 있다는 점이다!

KRNN(q)로 예를 들자면, 어떤 특정 박물관을 가장 가까운 k번째 박물관으로 가지는 호텔들을 구하는 것을 들 수 있다.

즉 지금까지는 호텔을 기준으로 박물관을 찾았다면, 이번에는 특정 박물관을 기준으로 호텔을 찾는것이다.

 

---

 

4. Similarity Join Query

서로 가까운 distance를 갖는 object들을 묶는 것이다.

위 그림을 보면 좀 더 쉽게 이해 할 수 있을 것이다.

서로 5분 거리에 있는 호텔과 박물관의 쌍을 모두 찾는 것을 예로 들 수 있다.

 

---

 

5. Combined Queries

 

두 쿼리를 합친 것이다.

Range 쿼리와 k근접이웃 쿼리를 합친다면,

처럼 표현할 수 있다.

k번째 이하로 가까우면서 동시에 r보다 적게 떨어져 있어야 하므로 그 개수가 K보다 작을 수도 있다.