R-tree, Kd-tree, BruteForce Query성능 비교

공간 데이터 관리 및 응용

Term Project

TermProject_20151607.tar

0.60MB

1.   Introduction

Range Query와 kNN Query는 공간 데이터 질의에 있어서 가장 많이 활용되는 질의 중 하나이다. 이 질의들을 하기 위해서는 공간 데이터를 저장할 자료구조가 필요한데, 대표적으로 kd-tree, R-tree 등이 있다.

공간 인덱스인 kd-tree, R-tree를 활용하여 range Query kNN query processing algorithm을 설계하고 질의 처리 성능을 비교 분석한다. 구체적으로 Brute-force, kd-tree, R-tree 방식을 사용하여 질의를 처리하고 질의처리에 걸리는 시간 및 질의 처리 과정에서 검사되는 객체의 수를 검사한다.

2.   Pseudo Code

1)   R-tree

RangeQuery(QueryNode q,QueryPoint p Radius r) If q is leaf            For child in q.childs                      If mindist(child,p) <= r                                 Push child to query result Else            For child in q.childs                      If mindist(child,p) <= r                                 RangeQuery(child,p,r)

(#1 min_dist > Kth actual_dist, #2 actual_dist > Kth minmax_dist #3 min_dist > Kth minmax_dist)
kNN Query의 경우 best fit search 방식에 3가지 pruning 방식을 적용하였다.

 

kNNQuery(QueryPoint p, integer K) avl.push(root, 0.0) r1, r2 = DOUBLE_MAX while avl is not empty            cur = avl.pop()            cur.visit = 1            for child in cur.childs                      mindist = MINDIST(child,p)                      minmaxdist = MINMAXDIST(child,p)                      if cur is leaf and mindist < r2 //PRUNNING #2                                 if size of result_queue < K                                            result_queue.push(child,mindist)                                 else if mindist < r                                            result_queue.pop()                                            result_queue.push(child,mindist)                                 if size of result_queue == K                                            r1 = DIST(result_queue.top, p)                      else if mindist < r1 and mindist < r2 //PRUNNING #1, #3                                 avl.push(child,mindist)                      if size of minmax_queue < K                                 minmax_queue.push(child,minmaxdist)                      else if minmaxdist < r2                                 while minmax_queue is not empty and                                                      minmax_queue.top().visit == 1                                            minmax_queue.pop()                                 minmax_pq.push(child,minmaxdist)                      if size of minmax_queue == K                                 r2 = minmax_pq.top().minmaxdist                      else r2 = DOUBLE_MAX

 

2) kd-tree

RangeQuery(QueryNode q,QueryPoint p, radius r) If dist(q,p) <= r            Result_queue.push(q,dist(q,p))   Caculate left rect and right rect of q Cacluate query_circle whose radius is r and center is p If q.left exists and isOverlap(left_rect,query_circle)            rangeQuery(q.left,r) if q.right exists and isOverlap(right_rect, query_circle)            rangeQuery(q.right,r)

kNNQuery(QueryNode q,QueryPoint p, integer K) node_pq.push(root, DIST(root,p)) r = DOUBLE_MAX while node_pq is not empty            cur = node_pq.pop()            if size of result_pq < K                      result_pq.pop()            else if dist(cur,p) < r                      result_pq.pop()                      result_pq.push(cur)            if size of result_pq == K                      r = result_pq.top().dist            i = cur.depth % 2 if p.x[i] – r <= cur.x[i] and cur.left      node_pq.push(cur.left, DIST(cur.left, p)) if p.x[i] + r >= cur.x[i] and cur.right      node_pq.push(cur.right, DIST(cur.right,p))

 

3.   Dataset and experiment

1)   Point Data set (각 100만개의 point data set)

Uniformed_dataset.txt

Clustered_dataset.txt

Gaussian_dataset.txt

이 Point Data set은 반드시 ./TermProject_20151607 폴더 안에 위치시켜야한다.

2)   Range query data set

Query point는 랜덤하게 정해진다.(Uniformly random)

Range_(dateset name).txt                                                    kNN_(dataset name).txt

Radius = 5.0 10.0 20.0 30.0 40.0 50.0                           K = 1 10 20 30 40 50 60 70 80 90 100

                      

      

FILE FORMAT

-      First line : Dataset file path

-      Second line : Option : 0 (range), 1 (knn)

-      From third line : Query data : query point \n Radius or K

3)   Experiment

Python code를 이용해 pivot을 랜덤하게 생성하고 range knn query에 필요한 dataset file을 /inputfiles에 만들어준다. 그 후 각 query data set을 읽어들여 실행파일을 컴파일 및 실행하고 outputfile을 /outputfiles에 생성한다.

마지막으로 Bruteforce를 기준으로 Kdtree output Rtree output을 비교하여 query result가 모두 같은지 확인한다.

모두 같으면 make output외에 아무런 표시가 뜨지 않으며 만약에 다르면 MISMATCH라는 문구가 뜬다.

실험 결과는 ./outputfiles/ 에 저장되며, Query result는 실행 코드에 따라 /BForce, /KDTree, /RTree에 저장되며 이는 각 질의code의 Correctness를 검증하는데 쓰인다.

시간 측정 결과는 (query name)_(dataset name).txt 에 저장되며

각 파일 안에는 query point에 대한 정보와 각 실행파일과 query data에 따른 실행시간이 ms단위로 기록되어있다.

 

4.   Result

총 30개의 pivot point를 random하게 뽑고, 각 pivot point마다 Range query, kNN query를 수행한 후 평균을 내었다.

Range query의 경우 radius = (5, 10, 20, 30, 40, 50) 총 6개를 테스트하며

total query = 6(#query) * 3(#tree) * 3(#datasets) = 54

kNN query의 경우 K = (1,10,20,30,40,50,60,70,80,90,100) 총 11개를 테스트한다.

total query = 11(#query) * 3(#tree) * 3(#datasets) = 99

pivot 마다 총 153번의 Query를 진행하며 pivot의 수 가 30개 이므로

4590 번의 Query를 진행하였다.

1)   Range Query

-    
Range Uniformed

Radius	Rtree	KDTree	Bforce
5	101.9	96.16667	6741.933
10	260.3333	235.3	6812.533
20	614.2333	653.5	7179.733
30	1195.1	1270.767	7558.8
40	1965.833	2104.333	7877.033
50	4068.867	4304.433	9631.933

 

-    
Range-gaussian

Radius	Rtree	KDTree	Bforce
5	9.266667	12.53333	7040.267
10	28.56667	32.63333	7044.8
20	170.6667	186.5	7147.033
30	372.5667	436.2667	7216
40	793.7	904.3667	7577.333
50	1509.333	1699.1	8030.167

-    

Range-clustered

Radius	Rtree	KDTree	Bforce
5	5.766667	9.533333	6869.5
10	24.9	38.53333	6783.5
20	187.0667	221.0667	6900.867
30	620.1667	662.0667	7252.167
40	1005.167	1059.967	7555.467
50	1668.2	1703.467	7870.433

2)   kNN Query

-     kNN-uniformed

K	Rtree	KDTree	Bforce
1	874.9	604.5667	11259.07
10	692.1333	1286.467	11362.4
20	818.4667	1474.4	11420.2
30	809.1	1659.9	11482.9
40	839.7333	1848.467	11581.87
50	987.9667	2009.067	11462.53
60	931.2	2143.867	11490.4
70	945.8	2278.233	11572.37
80	960.6333	2418.867	11628.4
90	1024.3	2575	11724.8
100	979.5	2659.533	11827.77

 

 

-     kNN-gaussian

K	Rtree	KDTree	Bforce
1	266.2333	2828.733	11254.8
10	264.4	10939.07	11322.2
20	331.7667	14587.33	11383.77
30	354.4	17684.73	11421.27
40	386.7667	20211.2	11457.17
50	432.4333	22411.73	11468.6
60	496.2	24420	11545.53
70	589.4667	26275.5	11558.77
80	488.2333	27677.57	11670.97
90	514.2	29162.47	11730.2
100	541.7667	30427.37	11744.77

 

 

-     kNN-clustered

K	Rtree	KDTree	Bforce
1	313.5333	13644.87	11216.43
10	395.2	20350.8	11320.43
20	436	22437.33	11351.67
30	477.6333	23819.07	11466.4
40	524.7	24917.6	11516.6
50	541.1	25834.97	11572.6
60	598.4	26553.7	11560
70	631.7667	27195.2	11544.63
80	636.3	27712.77	11599.03
90	762.9333	27964.4	11686.63
100	808.2	28446.27	11762.07

 

 

 

1)   Range Query

Range Query의 경우 Clustered, Gaussian, Uniformed data set 모두 RTree, KDTree, BruteForce순으로 빨랐고, 속도면에서는 RTree와 KDTree는 별로 차이는 없었으나, BruteForce의 경우 크게 느린 것으로 나타났다.

또한 Radius가 늘어날수록 질의 시간이 비례하여 늘어나는 것을 확인하였다.

2)   kNN Query

kNN Query의 경우 Range Query와는 다르게 dataset 별로 차이가 존재하였다.

먼저 Uniformed data의 경우 Range와 비슷하게 Bruteforce에 비해, RTree와 KDTree과 확연히 속도가 빠름을 볼 수 있다. Gaussian Data, Clustered data의 경우는 KDtree의 소요 시간증가 가 Bruteforce가 커, K = 20 부터는 KDTree가 BruteForce보다 훨씬 느려짐을 확인할 수 있었다. Rtree의 경우 KDTree와 Bruteforce보다 확연히 빨랐다.

5.   Discussion

RTree는 어떤 dataset(uniformed, Gaussian, Clustered)이든 어떤 Query(Range,kNN)든 query time이 우수함을 확인하였다.

KDTree는 경우 range query의 경우 RTree와 유사하게 빨랐으나, kNN Query의 경우

Uniformed을 제외하고는 K가 증가함에따라 매우 급격하게 느려졌다.

그 이유는 Gaussian dataset의 경우 점점 중심 밖으로 나갈수록 rect의 범위가 넓어져 prunning이 잘 되지 않으며, clustered data set 역시 마찬가지 이유로 prunning이 잘 되지 않기 때문이다.