Rena Makise

Rena Makise

Thrilling Dream

k-Nearest Neighbor Queries

K-Nearest Neighbor(K-NN) Queries

요약

  • MMDB(멀티미디어 데이터베이스)와 GIS(지리정보시스템)에서 가장 자주 발생되는 쿼리타입은 특정 공간에서 주어진 포인트에 가장 가까운 k개의 이웃을 찾는 쿼리이다.
  • 실세계의 모든 데이터는 하나의 점으로 표시가 된다. 특정한 점에서 가장 가까이에 있는 것이 가장 비슷한 노드이다. 이것을 찾는 문제를 푸는 것
  • 엑스레이를 찍어서 실제로 암이 있는 사진과 비슷하다고 하면 내가 암이 있을 확률이 굉장히 높은 것. 이렇게 유사도를 측정하는 것이 굉장히 중요하다.
  • 마찬가지로 주식을 샀는데 이 주식이 오를것인지 내릴 것인지, 기존의 정보와 유사도를 찾는 것이 굉장히 중요하다.
  • 이것을 찾기 위한 branch-and-bound 알고리즘. R트리 기반.

Introduction

  • k-NN 쿼리의 예
    • 특장한 쿼리 이미지와 가장 비슷한 k 이미지를 찾아라 (얼굴을 주고 비슷한 연예인을 찾아라 같은거)
    • 현재 이 지점에서 가장 가까이에 있는 호텔을 찾아 주시오
  • k-NN 쿼리의 효율적인 프로세싱을 위해서는 특별한 데이터 구조가 필요하다. 이것이 R트리. 인덱스 구조가 없으면 찾을 수가 없다. 따라서 색인 구조가 굉장히 중요하다.

  • Fanout (branching factor)

    • 한 노드가 포함할 수 있는 최대 엔트리의 갯수
    • R-tree search의 퍼포먼스는 disk accesses(reads)의 수로 표현이 된다. 디스크를 몇 번 액세스하는가로 해당 search 퍼포먼스, 또는 인덱스 구조의 퍼포먼스를 평가한다.

  • k-NN search에서 ordering(어떤 길을 먼저 추적할 것인가)을 위한 두 가지 metrics

    • query point(모든 데이터는 하나의 점으로 표시된다)가 P고 object(실제 DB에 있는 데이터)를 O라고 할 때,
    1. P와 O사이의 최단거리(MINDIST)를 계산
      • 모든 데이터는 점으로 표시되기 때문에 두 점간의 거리가 가까울수록 두 개의 데이터가 실제로 비슷하다고 보는 것.
    2. minimum of the maximum possible distance(MINMAXDIST)를 계산. 이것은 뒤에 설명
    • 이러한 metric을 써서 어떤 순서대로 R트리를 탐색할 것인지를 결정.
    • MINDIST는 lower bound, MINMAXDIST는 upper bound를 결정한다. 이것을 가지고 탐색 공간을 줄이는데 사용한다.

Minimum Distance(MINDIST)

  • Def.1

    • 크기가 n인 유클리드공간 E(n) 속의 직사각형 R에서 두 개의 포인트 S와 T로 표현이 된다.

    • R 트리에서는 특정한 오브젝트가 있다. 토끼 그림이 있다고 쳐보자. 이 토끼 그림을 그대로 넣긴 복잡하니까 근사화시킨다. 이 그림을 박스로 표현한다. 이 박스가 지난 시간에 배운 MBR(minimum bounding rectangle). 이 MBR울 S와 T로 표시한다.

  • Def.2 : MINDIST(P, R)

    • 위의 x와 y사이의 거리는 피타고라스의 정의를 이용해서 구할 수 있다.

    • 논문에서는 실제적인 거리보다 상대적인 거리를 중시하기에 계산하기 힘든 루트를 빼고 $d^2$을 구한다.

    • 이 $d^2$이 가장 작은 것이 제일 유사한 오브젝트라 본 것.

    • P는 쿼리 포인트, R은 특정 오브젝트를 나타내는 MBR. 이 두 점간의 최단 거리는 위의 공식으로 표시

    • 위 식은 그 위의 $d^2$식과 같다.

  • Theorem 1

    • 쿼리 포인트 P가 있고 특정 오브젝트를 포함하는 MBR R이 있는데 P에서 MBR R까지 거리는 실제 P에서 특정오브젝트 O까지의 거리보다 작거나 같다. 당연한 것. 둘러싸고 있으니까.

  • Lemma 2 : The MBR Face Property (중요)

    • 특정 MBR의 모든 페이스는 DB에 있는 특정 오브젝트의 최소한 한 점을 포함한다.
    • MBR은 실제 오브젝트의 특정 오브젝트와 최소 한 점에서 만난다는 것을 의미
    • MBR의 특정 면과 실제 오브젝트와 만나는 최소한 한 점이 존재한다는 것을 의미

Minmax Distance (MINMAXDIST)

  • MBR 속에 존재하는 어떤 오브젝트와 쿼리 포인트간의 upper bound를 조성

  • upper bound라는 것은 이 거리와 같거나 작은 쪽에서는 반드시 내가 원하는 오브젝트가 존재한다는 것을 보장하는 것을 의미

  • k는 차원

  • 각 차원마다 MINMAXDIST의 후보를 뽑는다.

  • 각 차원 라인에서 해당 오브젝트가 어디에 있을 지 모르기 때문에 보수적으로 쿼리포인트와 R의 제일 멀리 있는 포인트와의 거리를 MINMAXDIST의 후보로 선택한다.

  • 그 후보들 중에서 최소의 거리를 최종적으로 선택한다. min.

  • MINDIST에는 찾고자 하는 오브젝트가 없을 수도 있지만, MINMAXDIST보다 같거나 작은 거리 속에는 반드시 내가 원하는 오브젝트가 존재한다는 것을 보장

Nearest Neighbor Search Algorithm

  • 가장 가까이에 있는 이웃을 찾는 알고리즘

  • 얼굴을 주고 가장 비슷한 얼굴을 찾아주시오. 음악을 주고 해당 음악을 찾아주시오 등.

  • Example

    • 현재 내가 있는 위치에서 가장 가까이에 있는 주유소를 찾아주시오라는 쿼리.
    • 먼저 R트리의 루트로 들어온다. 루트로 들어오면 루트의 차일드 노드 1, 2, 3이 있다.
    • 루트 노드에서는 차일드 노드의 MBR과 포인터를 가지고 있다. 그 중에서 현재 위치와 가장 가까이에 있는 노드를 먼저 탐색한다.
    • 위 그림에서는 2번 속에 있으니까 2번과의 거리가 0이므로 2번을 먼저 탐색한다.
    • 물론 내가 원하는 데이터가 1번과 3번에 들어 있을 수도 있으므로 자료구조를 하나 세팅해서 1번과 3번을 세이브해둔다. 단, 1, 3중에 1이 더 가까우므로 1, 3 순서로 세이브를 해 둔다. 세이브를 해 둔다는 것은 탐색이 끝난 후 돌아와서 다시 탐색을 하겠다는 의미.
    • 2번으로 내려오니까 7, 8, 9가 존재. 그 중 9번이 제일 가까우므로 7, 8은 다시 자료구조를 하나 세팅해서 가까운 순서로 정렬해서 세이브를 해 둔다. 그리고 9번으로 내려간다.
    • 9번으로 내려가보니 9번은 leaf 노드다. leaf노드는 실제 데이터를 가지고 있으므로 현재 위치와 데이터간의 실제 거리를 계산할 수 있다. 따라서 임시로 ANSWER라는 자료구조를 하나 만들어 해당 자료구조에 가장 가까운 데이터를 세이브해둔다. 이 주유소가 제일 가깝다고 SAVE해둔다. 물론 다른 주유소를 전부 다 찾아본건 아니므로 이게 최종 답이라고는 할 수 없다.
    • 그런데 7번과 8번까지의 거리가 ANSWER와의 거리보다 더 멀기 때문에 방문할 필요가 없다. 이렇게 다시 위로 올라간다.
    • 1번 노드는 ANSWER와의 거리보다 더 가깝기 때문에 일단 방문할 필요가 있다. 하지만 3번 노드는 더 멀기 때문에 방문할 필요가 없다.
    • 1번노드로 내려와보니 4, 5, 6노드가 존재한다. 하지만 이 모든 노드들과의 거리는 ANSWER와의 거리보다 더 멀기 때문에 방문할 필요가 없다.
    • root로 올라와보니 모든 리스트가 비어있다. 따라서 종료.

  • 이 알고리즘을 통해 기존의 데이터베이스를 R트리를 색인구조로 하고, 새로운 데이터가 들어왔을 때 R트리상에서 색인구조를 통해 가장 유사한 것을 찾는 데 k-NN을 사용.