VA-File

VA-File

요약

• Dimensionality Curse (차원의 저주)
  • 색인 성능이나 검색 성능은 차원이 증가할수록 기하급수적으로 나빠진다.
  • B트리는 1차원 데이터를 처리, R트리는 2차원 이상의 임의의 차원 데이터를 처리
  • 기존의 인덱스 메소드는 전부 데이터 파티셔닝 인덱스 메소드였다. (트리형태)
  • 이렇게 나눔으로써 탐색에서 불필요한 탐색 범위를 줄일 수 있다.
  • 따라서 모든 자료구조를 트리형태로(B트리, R트리) 나타냈었다.
  • 차원이 저차원일때는 일반적으로 잘 동작한다. 하지만 차원이 증가하면 성능이 기하급수적으로 나빠진다.
  • 내가 고려해야될 컴포넌트의 갯수가 차원. 컴포넌트의 갯수가 굉장히 늘어난다.
  • 기존의 데이터 파티셔닝 인덱스 메소드(트리형태)로는 도저히 고차원 문제를 해결할 수가 없다.
  • 따라서 Vector-approximation file(VA-file)이 등장
    • 실세계의 모든 포인터는 n차원 상에서의 하나의 점으로 표시가 가능
    • 데이터를 있는 그대로 쓰기에는 양이 너무 많으므로 이를 간략화시켜서 점으로 표현
    • 줄어든 간소화 데이터를 시퀀셜 스캔한 후 내가 찾고자 하는 후보가 될 만한 것들만 모은다. (99%가 잘려나감)
    • 이 1%이하로 떨어진 남은 데이터를 오리지널 데이터로 읽어서 그 중에서 내가 찾고자 하는 데이터룰 k개 뽑아낸다,

Introduction

• Multidimentional Access Methods (기존 - 트리구조)
  • Data partitioning methods
    • 데이터를 파티셔닝한다.
    • 그 파티션 속에 들어가 있는 데이터를 클러스터링, 그루핑을 한다. (인접한 주유소들끼리 그루핑)
    • 이 파티셔닝을 통해 불필요한 탐색 범위를 잘라낸다.
  • 위의 방법은 저차원에서는 잘 동작하지만 차원이 높아질수록 기하급수적으로 성능이 떨어진다.
  • 차원이 대략 10을 넘어서면 단순한 시퀀셜 탐색이 오히려 데이터 파티셔닝 메소드보다 성능이 더 뛰어나게 된다.
  • 따라서 VA-file이 등장
• VA-file
  • flat file, 특정한 자료구조를 가지고 있지 않다,은 각 데이터에 대해 컴팩트하고 기하학적으로 근사화된 데이터. 특별한 자료구조 없이 그러한 데이터를 옆으로 쭉 모아놓은 것
  • 오리지널 벡터가 차지하는 공간의 10%에서 20% 정도로 단순화시킨다.
  • 더 작아진 근사화 데이터에 기초해서 대부분의 벡터들은 탐색시에 제외될 수 있다.

Analysis of k-Nearest Neighbor(k-NN) Search

• 쿼리 포인트가 하나 주어지면 k-NN, k번째로 가장 가까이에 있는 오브젝트까지 예상거리를 계산할 수 있다.

• 예상 거리를 계산하면, k-NN 쿼리를 spherical range query로 바꿀 수 있다.

  

• 각 점을 주유소라고 했을 때 내가 있는 곳에서 가장 가까이에 있는 주유소 세 개를 찾아주시오라는 쿼리를 던졌다고 가정해보자.

• 그러면 세 번째로 가장 가까이에 있는 점과의 거리를 반경으로 하는 원을 그리면 탐색 범위가 된다. 그 안에 있는 점은 다 찾아내야 한다.

• 그러면 이 동그라미와 겹치는 박스는 다 뒤져봐야된다.

• 그런데 이 빨간 동그라미가 커지면 커질수록 내가 검사해야하는 박스의 갯수가 많아진다. 따라서 가능하면 동그라미가 작을수록 좋다.

  

• 2차원 공간에서는 정사각형이 된다. 하지만 3차원 공간이 되면 정육면체가 된다.

• 이 때 꼭지점의 갯수는 2차원이면 $2^2$이고 3차원이면 $2^3$이 된다. 4차원이면 $2^4$, n차원이면 $2^n$개가 된다.

• 그 뿐만 아니라, 2차원 공간에서 박스에 내접하는 원을 그려보면, 이 원의 면적과 귀퉁이 면적을 비교해보면 원의 면적이 크다.

• 하지만 3차원으로 나가면, 구의 면적과 바깥의 귀퉁이 면적의 비율을 보면, 차원이 높아질수록 구의 면적이 줄어들고 바깥의 면적이 늘어난다. 따라서 차원이 늘어날수록 가운데 있는 면적보다 바깥의 면적이 기하급수적으로 늘어나게 된다.

  

• 따라서 차원이 늘어날수록 3개를 찾기 위한 면적이 훨씬 커지게 되니 겹치지 않는 박스가 없게 되어버린다. 따라서 모든 박스를 다 뒤져봐야 되게 된다.

  

• 차원이 높아질수록 데이터의 양을 늘인다 하더라도 데이터 공간이 여전히 희박하다. 따라서 데이터의 양은 영향을 끼치지 못한다.

  

• 특정한 하나의 노드가 방문되는 확률. 차원이 30이 되니까 모든 노드들을 100% 방문하게된다.

• 그래서 차원이 높아지면 검색 성능이 떨어지게 된다.

Difficulties of High Dimensionality

• 데이터 공간이 아주 희박하다. 아주 희박하게 데이터가 들어가있다.
  • 한 차원 높아질수록 제곱으로 공간이 팽창하기 때문
  • 따라서 파티셔닝이 잘 안된다.
    • 특정 임의의 포인트 Q가 특정 k-NN 안에 있을 확률이 매우 낮다.
    • 위의 경우 동그라미 안에 점이 3개 있었지만 차원이 높아지면 내가 동그라미를 아무리 키워도 안에 아무것도 안들어가게 된다.
    • 왜냐하면 꼭지점의 갯수가 기하급수적으로 늘어나고 가운데 있는 면적은 기하급수적으로 줄어들기 때문에
    • 따라서 아무리 키워도 거의 하나도 안들어오게 된다.
    • 100차원의 공간에서 k-NN의 dist를 0.5로 했을 때, 반지름을 0.5로 했을때 동그라미 안에 데이터가 들어올 확률은 약 ${1.9}/{10^{70}}$이 된다. 거의 안들어온다는 소리.
    • 그래서 파티셔닝이 안되고 데이터를 모으기도 어렵다.

Vector Approximation File(VA-File)

• 기본 아이디어
  • 다음과 같은 관찰로 부터 시작한다. 다차원 색인 메소드들은 고차원에서는 선형 탐색보다 성능이 나빠지더라.
  • 모든 디스크 블락을 다 뒤져야 하기 때문에.
  • 따라서 어차피 linear scan보다 못할 바에야 그냥 linear scan을 쓰겠다.
  • 하지만 linear scan을 하다보니 오리지널 데이터를 읽어야 할 양이 너무 많으니까 오리지널 데이터를 축약시켜서 간략화된 데이터를 만든 다음에 그것들을 읽겠다.
  • 그것들을 읽어서 후보가 되는 것들만 남기고 후보가 안된 것들은 걸러낸다.
  • 이때 99% 이상이 걸러진다. 따라서 1%미만 남은 것들만 오리지널 데이터를 읽어서 내가 찾고자 하는 것들, 유사한 데이터 k개를 뽑아내겠다.

Building the VA-file

• 1, 2, 3, 4가 오리지널 데이터이다.
• 이것이 보통 4바이트로 표현이 된다. 32비트. 이것이 두 개.
• 즉 오리지널 데이터는 64비트로 표시가 된다.
• 이 것을 각 차원마다 특정한 비트를 할당한다. 여기서는 두 비트를 할당
• 두 비트로 표시할 수 있는 데이터는 $2^2 = 4$개
• 이것을 같은 거리로 자른다.
• 그러면 1번 데이터는 0011, 2번은 1011, 3번은 0001, 4번은 1100으로 표시가 가능함.
• 즉 원래 64비트를 4비트로 줄일 수 있음. 이렇게 간소화한다.
• 그런데 이렇게 비트 수를 작게 하면 분별력이 떨어진다는 단점이 있다.
• 만약 위와 같이 1과 5가 다른 데이터임에도 불구하고 같은 값으로 간소화 될 수도 있음
• 이것이 간소화의 약점.
• 정리하면
  • 각 차원마다 $b_j$개의 비트를 할당한다.
  • 그러면 $2^{b_j}$개의 파티션이 생긴다.
• VA-file은 간소화된 데이터들의 배열.
• 위와 같이 간소화된 데이터를 그냥 연결해 놓은 것. 특정한 구조 없이 플랫 타입 구조다.

Lower and Upper Bounds

• search를 위해 특정 박스의 Lower Bound와 Upper Bound를 계산하는 방법
• 쿼리포인트 $p$, 그리고 오리지널 데이터 $p_i$
• 그리고 바깥에 둘러싼 박스가 간소화된 데이터
• 그러면 나는 쿼리포인트에서 오브젝트 $p_i$까지의 최단 거리와 최대 거리를 계산한다.
• 이 최단 거리가 $l_i$(Lower Bound)로 표시되고 최대 거리가 $u_i$(Upper Bound)로 표시된다.
• 2차원 상에서 두 점간의 거리는 피타고라스의 정리로 계산.
• 위 식에서 $p$승을 한다음에 $1/p$로 루트를 취하고 내부에서 Sum하는 것이 해당 공식을 의미.
• $w$는 해당 차원의 weight를 의미. 어떠한 데이터에 얼만큼 더 비중을 주겠다를 반영. 특정 대학에서는 영어보다 수학을 더 중요시 하겠다 하면 수학에 weight를 더 줄 수 있다.
• 최단거리는…
  • $x$축의 관점에서 박스 까지의 최단거리를 구한다.
    • $q$와 실제 오브젝트 까지의 lower bound
    • 하지만 실제 오브젝트는 근사화되어있기 때문에 정확히 어디에 있는지 모른다.
    • 그래서 해당 오브젝트를 포함하는 박스까지의 최단거리를 구한다.
    • 그런데 $q$는 해당 박스 속에 들어와있다.
    • 따라서 $x$축의 관점에서 최단거리는 0
  • $y$축의 관점에서 보면
    • $q$가 $y$축의 관점에서 보면 밑에 와 있다. 더 작다.
    • 이 경우는 각각 아래와 위까지의 거리를 반영
  • 그렇게 $l_{i,j}$를 구해서 다 더해서 지수승을 반영하면 $l_i$가 나온다.
• 최대거리는…
  • 최대거리에서는 $x$축의 관점에서…
    • 양 사이드와의 거리 중 더 먼 거리를 최대거리($u_{i,j}$)로 둔다.
  • $y$축의 관점에서는
    • $q$가 작은 쪽에 와 있다. 따라서 해당 공식을 반영
  • 그렇게 피타고라스의 정리를 사용해서 $u_i$를 구한다.

k-NN search algorithm

• 첫 번째 단계

  • 쿼리포인트와 각각의 approximation들간의 Lower Bound($l_i$)와 Upper Bound($u_i$)를 계산한다.
  • 그리고 $δ$를 지금까지 발견한 k번째로 큰 upper bound로 설정한다.
  • 만약에 특정한 approximation의 lower bound가 지금까지 찾은 k번째로 큰 upper bound인 $δ$보다 크다면 그것은 후보가 안된다. 따라서 그런것들은 전부 삭제시킬 수 있다.
  • 이러한 과정을 첫 번째 오브젝트부터 마지막 오브젝트까지 반복한다. 이를 통해 후보를 뽑아낸다.

• 두 번째 단계

  • 남은 후보들을 가지고 진행
  • $l_i$가 작은 순으로 하나하나씩 실제로 읽어서 마찬가지로 특정 lower bound가 지금까지 찾은 $δ$보다 크면 버린다.
  • 이렇게 해서 마지막에 남은 k가 내가 원하는 k번째로 가장 가까이에 있는 오브젝트가 된다.

• 실제 알고리즘

  

  • 1단계
    • 초기의 $δ$는 프로그램 랭귀지에서의 최댓값으로 세팅
    • 그리고 1부터 N(전체 데이터의 갯수)까지 루프를 돌린다. ($a_i$ : 실제 오브젝트)
      • $a_i$와 쿼리포인트까지의 lower bound와 upper bound를 계산
      • 그리고 특정 오브젝트의 $l_i$가 $δ$보다 작으면 후보로 들어가고 크면 버린다. 그리고 $ δ $를 다시 계산
      • 이렇게 후보를 뽑아낸다.
  • 2단계
    • 남은 후보들 중 실제 데이터를 읽어서 원하는 k개를 찾아낸다.
    • 이때도 남은 후보를 전부 다 읽진 않고
      • $l_i$를 읽어 실제 거리를 찾는다. 그리고 그것을 $δ$로 세팅한다.
      • 그런데 만약에 해당 $l_i$가 $δ$보다 크면 후보가 안된다. 그리고 $l_i$의 크기 순으로 읽기 때문에 자동적으로 뒤의 것도 날려버릴 수 있다.

• 이렇게 Sequential Scan을 통해서 차원의 저주 문제를 해결하고자 노력했다.