[논문 리뷰] The Case for Learned Spatial Indexes (2020.08.24)

The Case for Learned Spatial Indexes

논문 정보
제목	The Case for Learned Spatial Indexes
저자	Varun Pandey, Alexander van Renen, Andreas Kipf, Ibrahim Sabek, Jialin Ding, Alfons Kemper
소속	TUM, MIT CSAIL
저널	AIDB(AI Database), VLDB(Very Large Database)
주제	Computer Science > Databases
논문제출일	2020.08.24
인용수	53회 (2024.12.03 기준)

 

https://arxiv.org/abs/2008.10349

The Case for Learned Spatial Indexes

 

해당 논문 리뷰는 논문을 읽고 한국어 해석 + 부가 설명을 직접 추가하여 작성한 것으로

논문에는 없는 내용이 있을 수도 있으며

부정확한 내용이 있을 수도 있습니다 (..-_-..)

---

Abstract

GPS를 사용하는 수십억대의 기기와

Uber, Tinder, Facebook, Instagram 등과 같은 소비자 기반 application에서

매일 방대한 양의 공간데이터가 생성되고있다

 

이런 공간 데이터의 성장에 따라 공간 데이터를 효율적으로 처리하기 위한 연구가 진행되면서

공간 인덱스 방법(R-Tree, QuadTree 등..)들이 연구되고있다

 

그러다가 최근의 공간 인덱스 연구에서는

machine learning을 이용한 학습된 공간 인덱스를 도입하고 있다

 

따라서 본 연구에서는 최첨단의 학습된 다차원 인덱스 구조(Flood)를 활용한

기술을 5가지 classic 다차원 공간 인덱스에 적용하여

공간 range query를 처리할 수 있는 방법을 제안한다

 

본 연구는 다음 4가지 내용을 입증한다

 

1. machine learning을 활용한 partition 내 검색은 한 개의 차원을 기준으로 검색했을 때

이진 검색보다 11.79%에서 39.51%가 더 빠르다

2. classic 다차원 공간 인덱스의 대표 주자인 트리 구조에서

index lookup(인덱스 조회)가 병목현상이었으며,

이를 index partition을 linearlizing(선형화)하여 개선할 수 있다

3. 한 차원에서 filtering하고 machine learning index를 사용해하여 refine하는 방식은

두 차원에서 진행하는 것 보다 1.23배에서 1.83배 더 빠르다

4. learned index는 낮은 선택성(selectivity) 쿼리 성능에 상당한 영향을 미치지만

높은 선택성(selectivity) 쿼리에서는 효과가 적다

 

abstract만 보면 정확하게 무슨 말인지 잘 모르겠으니

자세하게 논문을 살펴보며 입증한 각 내용들이

정확하게 무슨 말인지 살펴보자

 

Introduction

공간 데이터의 양은 지속적으로 증가하고 있으며

NYC의 택시 승차 데이터셋은 2009년 이후 뉴욕시에서 발생한

27억 건 이상의 승차 및 하차 위치를 포함한다

그러나 이는 공간 데이터의 일부에 불과하다

인기 있는 승차 공유 서비스인 Uber에서는 2018년에만 100억 건의

승차를 완료하며 전 세계적으로 운영되고 있다

 

이러한 전례없는 위치 데이터 생성 속도는 시스템 확장(scale out),

데이터베이스 개선, 공간 쿼리 처리 향상, 현대 하드웨어와 컴파일 기술활용과 같은

다양한 연구를 이끌어왔다

 

최근 Kraska(2019) 등은 기존 데이터베이스 인덱스를 학습된 모델로 대체하여

정렬된 dataset에서 key의 위치를 예측하는 아이디어를 제안했으며,

이 연구를 통해 학습된 모델이 일반적으로 binary search(이진 검색)보다

빠르다는 것을 보여주었다

 

Kester(2017) 등은 메인 메모리 분석 엔진에서 최적화된 순차검색보다

인덱스 검색이 좁은 데이터 범위를 선택하는 쿼리에 더 적합다하는 것을 증명했다

 

이에 따라, 본 연구에서는 최근의 연구 결과를 바탕으로

학습된 인덱스 구조(Flood)에서 제안된 아이디어를

고전적인 다차원 인덱스에 적용하는 효과를 연구한다

 

고전적인 다차원 인덱스(classical multi-dimension index)는

Fixed-grid(고정 그리드), Adaptive-grid(적응형 그리드), Kd-tree, Quadtree, STR

5가지의 핵심 spatial partition 기술에 초점을 맞추었다

 

일반적으로 범위 쿼리 조회는 아래 3단계로 구성된다

1. index lookup(인덱스 조회)

2. refinement(세분화)

3. scanning

 

또 본 연구에서는 refinement(세분화) 단계에서

사용되는 일반적인 검색 기술(eg., binary search)을

learned models(eg., RadixSpline)으로 대체할 것을 제안한다

 

RadixSpline과 같이 학습된 모델을 검색 기술로 활용하면

특히 낮은 선택성(selectivity)을 가진 범위 쿼리에서

실행 시간을 상당히 단축할 수 있음을 발견했고

이는 Kester(2017)의 관찰과 유사하다

 

아래 차트에서 결과값을 확인할 수 있다

 

그렇다면 쿼리에서 선택성이란 무엇일까?

 

낮은 선택성(selectivity)이란 쿼리의 결과의 개수가

그렇게 많지 않은 쿼리를 뜻한다

 

예를 들어서 google map에서 주로 사용되는 쿼리는

'내 주변에 있는 카페를 알려줘'와 같은 유형인데

이는 주로 20~30개 정도의 쿼리 결과를 반환하기 때문에

이렇게 적은 수의 record를 다루는 쿼리를 낮은 선택성을 가진 쿼리라고 한다

 

반면에 주로 공간 데이터 분석에서 사용하는 쿼리는

'manhattan에서 발생하는 택시 요금의 평균 가격을 알려줘'와 같은 유형인데

이는 어마어마한 수의 record를 다뤄야하므로

높은 선택성을 가진 쿼리가 되는 것이다

 

이렇게 학습된 모델을 이용한 검색 기술이

낮은 선택성을 가진 범위 쿼리에서만 효과적인 이유는

record의 수가 많아질수록(선택성이 높아질수록) 실행시간에서

index lookup, refinement의 수행 시간 비율이 줄어들고

scanning 시간이 지배적으로 증가하기 때문이다

 

검색 기술은 refinement의 단계에서 사용하기 때문에

검색 기술을 학습된 모델로 변경한다고 해도

그렇게 큰 수확은 없게 되는 것이다

 

또한 1차원의 Grid partition 기술이 (eg., Fixed-grid, Apative-grid)

2차원(eg., Quadtree)에 비해서 학습된 모델에서

더 큰 이점을 얻을 수 있다는 점도 발견했다

 

본 연구는 학습된 모델과 결합된 다양한 공간 인덱싱 기술의

성능을 이해하는 데 있어 연구자와 실무자들에게 유용한 정보를 제공할 것이다

 

Approach

우선 range query processing(범위 쿼리 처리)가 어떻게

구현되었는지를 설명한다

 

그런 다음 본 연구에서 구현한 spatial partitioning techniques(공간 분할 기술)에

대해서 설명한다

마지막으로는, 각 partition 내에서 사용된 검색 기술에 대해서 설명한다

 

Range Query Processing (범위 쿼리 처리)

우선 범위 쿼리 처리가 무엇인지부터 알아보자

흔히 말하는 partitioning이란 데이터를 어떤 범위로 분할하는 것을 말한다

 

공간 데이터를 partitioning 한다는 것은 여러 곳에 흩어져있는 데이터들을

특정 범위로 쪼개서, 모든 데이터들을 각각의 범위에 포함되도록 분할하는 것이다

 

그럼 공간 데이터들은 각자가 속해있는 범위가 생길 것이고

범위 쿼리 처리란, 해당 범위에 위치한 모든 데이터를 찾아내는 것이다

 

공간 데이터에서의 범위 쿼리 처리를 예시로 든다면

point (위도, 경도)의 2차원의 데이터가 될 것이고

따라서 2개의 차원에서 하한과 상한을 가질 것이다

 

위에서 말했듯이 범위 쿼리 처리는 3단계로 작동한다

 

1. Index Lookup (인덱스 조회)

grid 혹은 tree 구조에서 범위 쿼리와 교차하는

모든 partition을 찾는다

 

이게 무슨 말이냐 하면

예를 들어

'현재 내 위치에서 3km 내부에 있는 모든 카페를 찾아줘'

라는 범위 쿼리가 들어왔다고 가정한다면

내 위치로부터 3km 내부에 있는 카페의 데이터들이

꼭 한 개의 partition 내부에만 있으리란 보장이 없다

그럴 때 데이터가 존재하는 모든 partition을 다 찾는다는 뜻이다

 

2. refinement

1번 단계에서 데이터가 존재하는 모든 partition을 찾으면

검색 기술을 활용하여 partition 내부에 있는 쿼리의 하한을 찾는다. 

 

이 말은, 범위 쿼리는 그 범위 내에서의 상한과 하한이 있다

그 하한을 index lookup 단계에서 찾아낸 partition 내부에서

찾는다는 뜻이다

 

물론 쿼리의 하한을 찾을 필요가 없을 때는 이 과정을 생략한다

예를 들어 partition이 범위 쿼리 내에 완전히 포함되는 경우에는

partition에서의 하한을 찾을 필요가 없기 때문에

단순히 해당 partition에 있는 모든 점들을 복사한다

 

3. scanning

이제 1번에서 Partition들을 찾았고

2번에서 partition 내부에서의 쿼리 하한을 찾았으면

해당 partition을 스캔해서 범위 조건에 맞는 data들을 찾는다

 

scanning 과정은 쿼리의 상한에 도달하거나

partition의 끝에 도달하는 즉시 중단된다

 

범위 쿼리 처리에서의 3단계 내용을 읽어보고 이해하다보면

기본적으로 데이터들이 정렬이 되어있어야 가능하다는 것을 알 수 있다

 

 

Partitioning Techniques (분할 기법)

데이터 셋을 공간적으로 분할하여 각 파티션(혹은 cell) 내의

객체들이 공간적으로도 가까이 위치하도록 하는 것을

spatial partitioning(공간 분할)이라고 한다

 

위 introduction에서 말했듯이 본 논문에서는 공간 분할 기법으로

Fixed-grid, Adaptive-grid, Quadtree, Kd-tree, STR을 사용한다

 

공간 분할 기법에는 크게 2가지가 있는데

1. space partitioning techinques (공간 분할 기법)

2. data partitioning techniques (데이터 공간 분할 기법)

이렇게 분류할 수 있다

 

2가지의 차이는 분류의 기준을

공간 그 자체에 두느냐 데이터에 두느냐의 차이이다

 

space partitioning techniques는 말 그대로

데이터를 보지 않고 그냥 공간 자체를 기준으로 분할하는 것이다

공간을 grid 혹은 사각형으로 고정된 방식으로 나누는 것이 대표적인 예이다

 

공간 데이터를 포함한 여러 가지 데이터의 경우

모두 고르게 분포하지 않고 다양하게 분포할 수 있다

어떤 곳에는 밀집하게, 어떤 곳에는 거의 데이터가 없을 수 있는데

그런 데이터의 분포를 고려하지 않고 분할하는 것이다

 

따라서 구현이 단순하며 데이터의 분포를 사전에 알 필요가 없고

각 partition에 포함되는 데이터의 개수를 고려하지 않는다

그러나 데이터가 균일하지 않거나 특정 영역에 밀집된 경우

비효율적인 분할이 발생할 수 있다는 단점이 있다

 

space partitioning techniques의 대표적인 예로는

Fixed-grid, Adaptive-grid, Quadtree가 있다

 

 

반면에, data partitioning techniques는

데이터를 기준으로 분할하며, 데이터의 위치와 분포에 따라 Partition을 정의한다

 

데이터가 분할된 공간 내에서 어떻게 분포되어있는지를 고려하며

각 partition에 포함되는 데이터의 밀도와 개수가 분할 결과에 영향을 주게 된다

 

이러한 data partitioning techniques의 장점은

데이터의 밀집도에 따라 동적으로 파티션을 생성하기 때문에

공간을 좀 더 효율적으로 사용할 수 있다는 것이다

 

하지만 데이터의 분포에 따라 분할 비용이 증가하거나

특정 케이스에서는 성능 저하가 발생할 수 있다는 단점이 있다

 

대표적인 예시로는

Kd-tree, STR, R-tree 방식이 있다

 

 

(1). Fixed-grid & Adaptive-grid

 

grid 방법은 주로 디스크에서 레코드를 최적화하여 검색하기 위하여 설계되었다

그리드에서 나눠진 cell은 grid page에 해당하며

경계에 포함된 data는 data page에 저장된다

따라서 각 cell은 data page를 인덱싱하기 위해 포인터를 저장한다

이렇게 cell과 data page간의 mapping을 grid directory(그리드 디렉토리)라고 한다

 

Fixed-grid(고정 그리드)에서는 그리드의 subdivision line(구분선)이

모두 동일한 간격으로 구분되어야한다

하지만 Adaptive grid(적응형 그리드)는 데이터의 분포에 따라

구분선의 간격이 조정될 수 있다

 

이 연구에서 사용하는 Flood는 d차원 데이터에 대해 최산 상태의 학습된 다차원 인덱스로

d-1차원에서 그리드를 사용해 데이터를 분할하고 마지막 차원을 정렬차원으로 사용한다

 

 

(2). Quadtree

 

Quadtree는 공간을 분할하는 트리 데이터 구조이다

Quadtree는 rectiliner hyperplane(직선형 초평면)을 사용하여 공간을 분할한다

직선형 초평면이란 어떤 차원이 있으면 차원의 축이 있을텐데

그 축의 수직으로 직선을 그어 공간을 분할하는 방법을 얘기한다

 

quadtree는 이진트리와 달리 d차원에 대해서 2d제곱개의 자식을 갖는다

따라서 point data는 2차원 데이터이므로 총 4개의 자식을 갖게된다

 

공간은 재귀적으로 네개의 사분면으로 분할되며

각 사분면의 객체 수가 사전에 정의된 임계값보다 작아질 때까지 분할이 계속된다

 

Quadtree는 일반적으로 balanced tree가 아니며

객체 밀도가 높은 영역에서는 더 높은 수준으로 분할된다

 

 

(3). k-d tree

 

k-d tree는 공간을 직선형 초평면을 사용해

재귀적으로 동일한 크기의 하위 공간으로 나누는 이진 검색트리이다

 

분할에 사용되는 초평면은 각 단계에서 구분자(discriminator)라고 불린다

예를 들어 2차원 데이터에서는 x축과 y축에 수직인 분할 초평면이 생기며

이는 x-discriminator, y-discriminator라고 불린다

 

초기의 k-d tree는 데이터의 분포를 신경쓰지않고

공간을 동일한 크기로 분할했지만, 최근에는 데이터 중심적(data-aware)으로

작동할 수 있다고 한다

 

따라서 단순히 공간을 기준으로 이등분 하는 것이 아닌

데이터의 중간값을 기준으로 데이터를 두 부분으로 나누어

공간을 분할하고 균형잡인 이진트리를 만들어낸다

 

(4). Sort-Tile-Recursive (STR) packed R-tree

 

Sort-Tile-Recursive는 R-tree를 채우기 위한 패킹 알고리즘으로

공간 활용도를 극대화하는 것을 목표로 한다

 

R-tree에서 packing이란 데이터를 효율적으로 배치하여 공간활용도를 극대화하는 방법으로

전통적인 r-tree는 데이터를 하나씩 삽입하면서 노드를 생성하고 트리를 구성하지만

packing은 모든 데이터를 한 번에 삽입하며 트리를 구성한다

packing을 통해서 r-tree 구조의 공간 활용을 극대화 할 수 있고

tree의 균형을 유지할 수 있으며

데이터를 하나씩 삽입할 때 발생하는 오버헤드를 줄일 수 있다

 

STR packing의 핵심 아이디어는 데이터 공간을 S x S grid로 나누는 것이다

 

STR 패킹 과정은 다음과 같다

1. 정렬

데이터를 x축을 기준으로 정렬한 뒤, S개의 vertical slices(수직 슬라이스)로 나눔

2. 슬라이스 분할

각 vertical slices 내에서 y축 기준으로 정렬한 뒤

길이가 N인 그룹으로 나누어 node에 패킹하여 horizontal slices(수평 슬라이스) 생성

3. 재귀적 반복

 

쉽게 설명하면 STR 알고리즘에서는

데이터를 우선 x좌표 기준으로 정렬(수직) -> y좌표 기준으로 정렬(수평)

데이터를 노드의 용량 N에 맞게 그룹화를 한다

그렇게 되면 각 그룹은 한 개의 R-tree node가 되는 것이다

이렇게 그룹화된 데이터를 기반으로 노드를 생성하며

그 안에서 다시 정렬과 그룹화 과정을 재귀적으로 수행하며 트리를 생성하는 것이다

 

이런 방식으로 R-tree를 패킹하면 마지막 노드를 제외한

모든 노드가 완전히 채워지게된다

 

Search Within Partition

아까 위에서 봤겠지만 학습된 인덱스 구조는

기본적으로 데이터가 정렬이 되어있어야한다

따라서 다차원 데이터에서는 어떤 한 차원을 기준으로 데이터를 정렬해야한다

 

2차원 데이터인 point에서는 위도와 경도 중 한 개를

정렬 차원으로 선택해야하기한다

본 실험에서는 경도(latitiude)를 기준으로 정렬했다

 

따라서 정렬된 데이터 내부에서 검색을 할 때

본 연구에서는 Binary Search 대신 다른 방법론으로

학습 기반 인덱스 구조인 RadixSpline을 사용했다

 

RadixSpline이란 대규모 데이터셋에서 빠른 검색 및 조회를

지원하기 위한 학습 기반 인덱스 구조인데

이는 두 가지 핵심 요소로 구성된다

1. Spline Points

정렬된 데이터 배열에서 주어진 키 값의 위치를 예측하기 위한 제어점

2. Radix Table

특정 키 값이 속한 Spline Point 범위를 빠르게 찾기위한 자료구조

 

RadixSpline의 검색 작동 방식은 다음과 같다

우선 조회해야할 key가 들어오면 RadixTable에서

조회 key가 속하는 Spline Point를 빠르게 확인한다

 

Spline Point 사이에서 linear Interpolation(선형 보간법)을

사용해 key값의 위치를 계산하고

이 계산값은 데이터 배열 내의 근사 위치로 사용된다

위에서 계산한 예측값에 오류가 있을 경우

로컬 검색을 통해 실제 key 값의 정확한 위치를 보정한다

 

RadixSpline은 논문 작성 시점 기준으로는 정수 값만 처리할 수 있기때문에

오픈소스 구현을 수정하여 부동소수접 값도 처리할 수 있도록 변경했다

 

RadixSpline은 주로 Binary Search의 대안으로 많이 사용되며

두 기법의 차이점은 아래와 같다

 

Evaluation

단일 스레드

Ubuntu 18.04

Intel Xeon E5-2660 v2 CPU (2.20 GHz, 10코어, 3.00 GHz 터보)

256GB DDR3 RAM

환경에서 모든 실험이 진행되었다

 

NUMA(비균일 메모리 접근)을 피하기 위해

스레드와 메모리를 하나의 노드에 바인딩했으며

cpupower 명령어를 사용하여 CPU 스케일링을 비활성화했다

 

Dataset

evaluation에는 다음 세 가지 데이터셋이 사용되었다

 

1. 뉴욕시 택시 승차 데이터(NYC Taxi Rides)

2014년 - 2015년 동안의 3억 500만건

2. 뉴욕시 지역의 위치 기반 트윗 데이터 (NYC Tweets)

Twitter API로 수집된 8300만 건의 트윗 데이터

3. 오픈스트리트맵(OSM)

All Nodes(Points) 데이터셋에서 추출된 2억건의 records

 

각 데이터셋에 대하여 2가지 유형의 쿼리를 생성했다

1. skewed query(편향된 쿼리): 데이터의 기본 분포를 따르는 쿼리

2. Uniform query(균일한 쿼리): 데이터 공간에 균일하게 분포된 쿼리

 

또한 앞에서 설명한 선택성(selectivity)에 대해서는

각 쿼리 유형에 대해서 선택성이 0.00001%에서 1.0%까지 범위인

6가지 다른 작업 부하를 생성했다

 

뉴욕 택시 승차 데이터에서(3억 500만건)

30개의 레코드부터 최대 300만개의 레코드까지 반환하는 쿼리가 생성된다

 

Tuning Partitioning Techniques

최근 다차원 데이터와 공간 인덱스에 대한 연구는

데이터와 쿼리에서 learning하는 것에 중점을 두고있다

 

이런 작업에서 learning을 하는 기본 아이디어는

특정 사용 사례에 최적화 할 수 있는

instance-optimized(인스턴스 최적화)가 가능하다는 점이다

 

이러한 효과를 연구하기 위해

위의 3가지 dataset에 대해 parition 크기를 조정하고

선택성이 높은 쿼리와 낮은 쿼리를 기반으로

skewed 쿼리와 uniform 쿼리에 대해 여러 실험을 수행했다

 

위 Figure 4는 skewed와 uniform 2가지 쿼리 유형에서

가장 낮은 선택성 작업에 대해서 인덱스를 튜닝(RadixSpline)했을 때의 결과이다

 

위 figure를 통해서 확인해보면

partiton 크기가 커짐에 따라 성능이 특정 partition 크기까지 개선되다가

그 크기를 초과하면 성능이 저하되는 것을 볼 수 있다

그리고 grid기반의 partitioning 기법들이 다른 기법들에 비해서

그 정도가 훨씬 크다는 것도 알 수 있다

 

 

grid 기반의 partitioning 기술에서 학습기반 인덱스를 사용했을 때

성능이 크게 향상된 것을 알 수 있다

skewed query의 경우 11.79%에서 39.51%까지 속도가 향상됐다

 

그러나 quadtree나 STRtree에서는 성능이 저하된 경우도 많았고

학습기반 인덱스가 큰 도움을 주지 못했다는 것을 알 수 있다

 

이러한 이유는 quadtree나 STRtree에서는

최적 파티션 크기가 매우 작기 때문인데

이러한 경우에는 학습 기반 인덱스의 추가 refinement cost가

성능에 부정적인 영향을 미치기 때문이다

 

 

figure 5는 Taxi Trips 데이터셋에서 낮은 선택성 쿼리에 대한

Fixed-grid 기술에서 파티션 수와 파티션 내 점의 수가

쿼리 런타임에 미치는 영향을 보여준다

 

numbers of points per partition이 증가하면

즉, numbers of partition은 감소하면

number of cells는 감소한다

하지만 동시에 scanned 되어야할 points는 증가한다

 

따라서 이 두 곡선이 교차하는 지점이 최적 구성으로

가장 낮은 query runtime에 해당하게된다

 

 

Quadtree와 같이 2개의 차원을 모두 필터링하는 구조는

대부분의 pruning 작업을 index lookup 시에 수행한다

따라서 이러한 구조에서 지배적인 비용은 partition 내에서

scan해야하는 점의 수이며 query runtime은 이 점의 수에 비례한다

 

따라서 scan 해야하는 점의 수를 최소화하려면

index lookup시 pruning 작업이 많이 필요하며

이는 더 많은 partition의 개수를 요구하지만

index lookup 비용은 증가하게된다

 

Range Query

이번 실험에선 학습 기반 인덱스를 위주로한 여러 인덱스 구조를 사용하여

range query(범위 쿼리)의 실행시간을 비교해본다

 

uniform query를 제외한 대부분의 경우에서

1차원 Schema (Fixed-grid, Adaptive-grid)가 우수한 것을 확인할 수 있다

특히 skewed query에서는 Quadtree보다 1.23배에서 1.83배 더 빠르다

 

여기서 Fixed-grid는 쿼리가 교차하는 첫 번째 partition을

단순히 offset 계산으로 찾기 때문에 index lookup시간이 거의 없다

하지만 Adaptive-grid는 이진탐색을 통해 찾기 때문에

index lookup 시간이 상대적으로 더 소요된다

 

또한, uniform query에서는 Quadtree가 Taxi Rides와 OSM 데이터셋에서

가장 우수한 것을 확인할 수 있다

 

이러한 결과가 나오는 이유는

Quadtree는 다른 인덱스 구조보다 교차하는 partiton 수가 적기 때문이다

 

또, uniform query일 경우, Quadtree는 주로 깊이가 얕고

데이터가 드문 영역만 탐색하기 때문에 uniform query에서 더 효율적일 수 있다

 

이러한 결과는 기존의 연구 결과와도 일치하고

Quadtree가 R*-tree나 Pyramid-Technique보다

uniform query에서 더 우수한 성능을 보였다는 점이 확인된다

 

 

Indexing Cost

Fixed-grid와 Adaptive-grid는 tree-based index보다

인덱스를 훨씬 빠르게 생성할 수 있다

Quadtree는 가장 느리게 생성되며

이는 최적의 설정을 위해 많은 partition을 생성하기 때문이다

 

Quadtree는 데이터보다 공간을 위주로 분할하기 때문에

partition의 데이터마다 불균형이 있다

하지만 Fixed-grid와 Adaptive-grid는 최적의 설정에서

큰 크기의 파티션을 생성하기 때문에

파티션 수도 상대적으로 적고 인덱스 크기도 상대적으로 작다고 한다

 

 

Related Work

Kraska(2018)등은 전통적인 데이터베이스 인덱스를 대체할 수 있는

학습 모델의 아이디어를 제시했다

이 모델에서는 데이터셋 내의 1차원 key의 위치를 예측하여

인덱스의 역할을 수행하였고

이후, 이러한 학습 기반 인덱스 아이디어를 공강 및 다차원 데이터로

확장하는 다양한 연구가 진행되었다

 

Flood는 메모리 내에서 작동하는 다차원 인덱스이다

데이터를 d차원 공간에서 grid로 나눈다

데이터와 query workload(쿼리 작업량)에 따라

grid 구성이 adpative하도록 설계한다

 

Qd-tree는 reinforcement learning(강화 학습)을 사용하여

쿼리가 접근하는 디스크 블록 수를 최소화하는 partitioning 전략을 생성한다

디스크 기반 다차원 인덱스에서 I/O 비용 절감에 초점을 맞춘다

 

LISA는 디스크 기반 학습 공간 인덱스이다

저장 공간 소비와 I/O 비용을 줄이는 동시에

range query, nearest neighbor query, insertions and deletion을 지원한다

 

ZM-index는 Z-order 공간 채우기 곡선(Z-order space-filling curve)와

기존의 학습 기반 인덱스(RMI)를 결합하였다

다차원 데이터를 1차원 공간으로 매핑 후 학습 가능한 모델을 통해 인덱스를 생성한다

 

ML-index는 기존 iDistance와 RMI의 아이디어를 결합하여

range query와 KNN 쿼리를 지원하도록 설계하였다

 

Conclusions and Future Work

본 연구에서는 최신 다차원 인덱스 기술인 Flood를 구현하였다

Flood는 Grid-file의 변형을 활용하여 point를 indexing하고

이를 5가지 classical 공간 인덱스에 적용하였다

 

그 결과 partition 내 binary search를 학습기반 인덱스로 대체하면

쿼리 실행 시간이 11.79%에서 39.51%까지 개선된다

또한 선택도가 낮은 쿼리일수록 학습 기반 인덱스의 성능 향상이 두드러지며

선택도가 높은 쿼리에서는 빠른 검색의 효과가 덜하다

 

데이터의 차원 별로 정리를 하자면

1차원 Grid partitioning에서는 학습 기반 인덱스를 사용하니

더 큰 효과가 있었다

왜냐하면 1D partition의 경우, 각 셀이 포함하는 데이터 포인트를

충분히 대표하지 못하기 때문에 추가 refinement작업이 필요하기 때문이다

 

2차원 tree partitioning에서는 1차원에 비해 학습 기반 인덱스의 효과가 적었다

하지만 1차원 partitioning은 적합한 파티션을 찾는 과정이

2차원보다 효율적이어서 쿼리 실행시간이 더 빠르다

 

향후 연구 과제는 크게 2가지가 있는데

본 연구에서는 Quadtree와 k-d tree에 대한 기본 구현을 사용했지만

Quadtree 셀 직선화(Hilbert 곡선을 사용, Z-order 곡선을 사용)하고

생성된 cell 식별자를 학습 기반 인덱스에 저장하는 방법을 연구할 필요가 있다

 

또 다른 한가지는

현재 본 연구는 RAM에 데이터를 모두 적재한 경우를 중심으로 진행했다

하지만 만약 디스크 기반 환경이라면 I/O 비용에 따라

성능이 결정될 가능성이 굉장히 높고

partition의 크기는 물리적 페이지 크기와 정렬될 때

성능이 최적화될 것으로 예상된다

따라서 불필요한 포인트를 포함하지 않고 파티션을 구성하는 것이 중요할 것이다

따라서 향후 연구에서는 디스크 환경 최적화를 중점적으로

다뤄야 할 필요가 있다