Layer-Based Indexing Method for Top-k Queries 임선영 책임연구원, 빅데이터 활용 연구센터, 숙명여자대학교 sunnyihm@sm.ac.kr 2017. 05. 16 (Tue.) 강원대학교 특강

Sun-Young Ihm Education Teaching Experience Projects Awards BS, MS, Ph.D. in SMWU (under prof. Young-Ho Park) Teaching Experience 2014 ~ 2016 : Programming, Database, etc. at SMWU, SWU Projects 2 Project Leader, 6 Manager/Developer Awards 1 Excellence Project Award, 3 Best Paper Awards. Journal Editing DB Research, KIISE

Sun-Young Ihm Publications Total 61 papers for 6 years (first author : 41 papers) 7 SCI(E) journal papers (the average of IF : 1.3) 7 SCOPUS journal papers 8 domestic journal papers (KCI journal) 18 international conference papers 21 domestic conference papers

Motivation [Top-k Query 예제] 중고차 검색 𝑓 𝑡 =0.2∗𝑦𝑒𝑎𝑟+0.5∗𝑝𝑟𝑖𝑐𝑒+0.3∗𝑚𝑖𝑙𝑒𝑎𝑔𝑒 No year price (백만원) mileage (1,000km) A 3 20 17 B 2 15 10 C 8 12 D 7 13 E 9 f(t) 15.7 10.9 9.6 10.3 9.9 Top-1 Top-2 Top-2: 중고차C, 중고차E

Motivation (cont.) Top-k query? 중고차 검색, 카메라 검색, 호텔 검색, 등 <중고차 검색> <카메라 검색> <호텔 검색>

Motivation (cont.) 효율적인 질의 처리를 위해서는 색인 구축이 필요 전체 데이터 대신 일부 데이터만 읽고 질의 처리를 하기 위해 색인 구성 기존의 계층 기반의 색인 생성 연구들은 고차원에서 사실상 사용이 불가능함 효율적인 질의 처리는 색인 구성 시간이 빠르고, 전체 계층의 수가 많을 수록 컨벡스 홀 : 기하급수적으로 증가하는 색인 생성 시간, 전체 계층의 수는 감소 스카이라인 : 전체 계층의 수 감소, 기준으로부터 방향(direction from origin)의 질의만 처리 가능 색인 구성 시간이 오래 걸릴수록 : 대용량, 고차원에서 색인 구성 불가 색인 갱신 어려움 전체 계층의 수가 적을 수록 : 계층에 포함되는 데이터 증가  질의처리 시 읽는 데이터 증가 (a) 색인 구성 시간 (b) 전체 계층의 수 차원 변화에 따른 컨벡스 홀과 스카이라인 구축 실험 결과

Motivation (cont.) 효율적인 질의 처리를 위해서는 색인 구축이 필요 전체 데이터 대신 일부 데이터만 읽고 질의 처리를 하기 위해 색인 구성 기존의 계층 기반의 색인 생성 연구들은 고차원에서 사실상 사용이 불가능함 효율적인 질의 처리는 색인 구성 시간이 빠르고, 전체 계층의 수가 많을 수록 컨벡스 홀 : 기하급수적으로 증가하는 색인 생성 시간, 전체 계층의 수는 감소 스카이라인 : 전체 계층의 수 감소, 기준으로부터 방향(direction from origin)의 질의만 처리 가능 (a) 색인 구성 시간 (b) 로그스케일로 표시 데이터 크기에 따른 컨벡스 홀 구축 실험 결과

Motivation (cont.) => 고차원의 데이터에 사용 가능한 새로운 개념의 다차원 색인 구성 방법의 필요 고차원의 데이터에서 Top-k 질의 처리가 가능한 색인의 부재 색인 구축 시간이 너무 오래 걸리고, 계층의 수가 적어 전체 데이터를 읽어야 하는 문제 존재 => 고차원의 데이터에 사용 가능한 새로운 개념의 다차원 색인 구성 방법의 필요

Contribution 색인 생성 시간과 정확도를 조절 가능한 AdaptCS (Adaptive Convex Skyline) 제안 한 방향의 질의 처리가 가능하도록 계층을 구성 가상의 한계점을 통해 불필요한 데이터 사전에 제거 가상의 한계점을 통해 색인 생성 시간과 정확도를 조절하는 적응적 방법 대용량 고차원 데이터를 위한 새로운 불균형 계층 UB-Layer (UnBalanced Layer) 제안 모든 방향의 질의 처리가 가능하도록 계층을 구성 차원을 분할하여 컨벡스 홀 생성 후 병합 차원을 분할하는 다양한 방법 제안 색인 구성 시간 감소, 전체 계층의 수 증가로 효율적인 질의 처리 가능

Related Work 계층 기반의 색인 구성 방법 데이터의 d개의 속성 값을 d-차원의 공간에 표현하고, 계층 리스트를 구성하는 방법 계층 리스트를 생성하는 방법으로는 스카이라인 방법, 컨벡스 홀 방법, 컨벡스 스카이라인 방법이 대표적 Optimally Linearly Ordered Set Property: top-i의 결과를 얻기 위해서는 최대 i번째 계층까지 데이터를 검색하면 top-i 결과를 얻을 수 있음 Layer list A2 A1 O objects A1 A2 t1 1 8 t2 7 2 t3 10 t4 5 11 t5 4 6 t6 t7 t2 t3 t4 t6 t5 t7 Layer[1] 8 Layer[2] t1 Relation R 1

Related Work (cont.) 스카이라인 방법 계층 리스트로써 스카이라인을 구축하는 방법. 장점 : 색인 구성 시간이 빠름 단점 : 고차원일수록 첫 번째 계층에 대부분의 데이터가 속함 Soft-Filter-Skyline (SFS) pre-sorts the input tuples according to the entropy value. Plane-Project-Parallel-Skyline (PPPS) partitions by coordinating the tuples using hyper-plane projection. Grid-Plane-Project-Parallel-Skyline(Grid-PPPS) first computes approximate skyline and partitions by grid based and hyperplane-projection based method. (a) Soft-Filter-Skyline (b) Plane-Project-Parallel-Skyline (c) Grid-Plane-Project-Parallel-Skyline

Related Work (cont.) 스카이라인 방법 계층 리스트로써 스카이라인을 구축하는 방법. 장점 : 색인 구성 시간이 빠름. 단점 : 고차원일수록 첫 번째 계층에 대부분의 데이터가 속함. Soft-Filter-Skyline (SFS) pre-sorts the input tuples according to the entropy value. Plane-Project-Parallel-Skyline (PPPS) partitions by coordinating the tuples using hyper-plane projection. Grid-Plane-Project-Parallel-Skyline(Grid-PPPS) first computes approximate skyline and partitions by grid based and hyperplane-projection based method. (a) Soft-Filter-Skyline (b) Plane-Project-Parallel-Skyline (c) Grid-Plane-Project-Parallel-Skyline

Related Work (cont.) 컨벡스 홀 방법 모든 기준점을 고려하여 가장 바깥의 데이터를 계층으로 구성하는 방법. 장점 : 스카이라인과 비교하여 각 계층에 적은 수의 데이터를 포함하며 모든 방향의 질의처리에 대한 결과를 구할 수 있음. 단점 : 스카이라인과 비교하여 높은 색인 구성 시간을 가짐. ONION constructs layers by computing the convex hull Approximate Convex Hull Index (aCH-Index) computes the convex hull based on the skyline layer. O3 O4 vC region O1 O2 (a) ONION (b) aCH-Index

Related Work (cont.) 컨벡스 스카이라인 방법 하나의 기준점을 고려하여 가장 바깥의 데이터를 계층으로 구성하는 방법. 장점 : 스카이라인과 비교하여 각 계층에 적은 수의 데이터를 포함. 단점 : 스카이라인과 비교하여 높은 색인 구성 시간을 가짐. Partitioned-Layer Index (PL-Index) computes the convex hull based on the skyline points. Approximate Convex Skyline (AppCSE) computes the convex skyline based on the skyline points with virtual points. subregion1 subregionm-1 subregion0 (a) PL-Index (b) AppCSE

AppCS (Approximate Convex Skyline) Sun-Young Ihm, Ki-Eun Lee, Aziz Nasridinov, Jun-Suk Huh and Young-Ho Park, "Approximate Convex Skyline: A Partitioned Layer-based Index for Efficient Processing Top-k Queries," KNOWLEDGE BASED SYSTEMS, Vol.61, pp.13-28, 2014.05. Constructing skyline step Partitioning step Layering step subregion1 subregionm-1 subregion0 X2 X1 O 2. Partitioning 1. Constructing skyline 3. Layering

Grid-PPPS Sun-Young Ihm, Aziz Nasridinov and Young-Ho Park, "Grid-PPPS: A Skyline Method for Efficiently Handling Top-K Queries in Internet of Things," JOURNAL OF APPLIED MATHEMATICS , Vol.2014 (2014), Article ID 401618, 10 pages, 2014.05.08. f e a c d g b h X2 X1 O Step 1: Approximate Skylining step i j Step 2: Grid-based Partitioning step Step 4: Local Skylining step Step 5: Merging step Step 3: Hyperplane-based Partitioning step

aCH-Index (Approximate ConvexHull) Sun-Young Ihm, Aziz Nasridinov and Young-Ho Park, "An Efficient Index Building Algorithm for Selection of Aggregator Nodes in Wireless Sensor Networks," INTERNATIONAL JOURNAL OF DISTRIBUTED SENSOR NETWORK, Vol.2014, 2014.04.07. O1 O2 O3 O4 region vC Step 1: Skyline Layering step Step 2: Partitioning step Step 3: Computing step

AdaptCS: Adaptive Convex Skyline Overview 3 Steps (a)스카이라인 단계: 가상의 한계점 vTHRES를 통해 불필요한 데이터를 사전에 제거 (b)분할 단계: 초평면 투영 기반의 분할 방법으로 데이터 공간 분할 (c)계층 생성 단계: 분할된 공간에서 컨벡스 스카이라인 계산 후 병합하여 계층 리스트 완성 일정 이상의 정확도를 유지하면서 색인 생성 시간을 줄임 정확도와 색인 생성 시간을 조절 가능함

AdaptCS: Adaptive Convex Skyline (cont.) 스카이라인 단계 가상의 점 vTHRES를 이용하여 불필요한 데이터 제거. vTHRES: 각 속성별 최소 값으로 이루어진 가상의 점. SFS algorithm [Sky]을 사용하여 스카이라인 생성. Steps of AdaptCS 스카이라인단계 분할 단계 계층 생성 단계 X2 O X1

AdaptCS: Adaptive Convex Skyline (cont.) 스카이라인 단계 가상의 점 vTHRES를 이용하여 불필요한 데이터 제거. vTHRES: 각 속성별 최소 값으로 이루어진 가상의 점. SFS algorithm [Sky]을 사용하여 스카이라인 생성. Steps of AdaptCS 스카이라인단계 분할 단계 계층 생성 단계 X2 vTHRES O X1

AdaptCS: Adaptive Convex Skyline (cont.) 스카이라인 단계 가상의 점 vTHRES를 이용하여 불필요한 데이터 제거. vTHRES: 각 속성별 최소 값으로 이루어진 가상의 점. SFS algorithm [Sky]을 사용하여 스카이라인 생성. Steps of AdaptCS 스카이라인단계 분할 단계 계층 생성 단계 X2 vTHRES a b c d e O X1

AdaptCS: Adaptive Convex Skyline (cont.) 스카이라인 단계 가상의 점 vTHRES를 이용하여 불필요한 데이터 제거. vTHRES: 각 속성별 최소 값으로 이루어진 가상의 점. SFS algorithm [Sky]을 사용하여 스카이라인 생성. Steps of AdaptCS 스카이라인단계 분할 단계 계층 생성 단계 X2 X2 X2 vTHRES vTHRES vTHRES O X1 O X1 O X1 min_vTHRES max_vTHRES mid_vTHRES

AdaptCS: Adaptive Convex Skyline (cont.) 분할 단계 초평면 투영 방식으로 데이터 공간 분할. 기존 연구(PL-Index, AppCSE)에서 사용하는 k-means 기반의 분할 방식과 비교하여 스카이라인 계산에 유리하게 분할됨. Steps of AdaptCS 스카이라인단계 분할 단계 계층 생성 단계 X2 vTHRES a b c d e O X1

AdaptCS: Adaptive Convex Skyline (cont.) 분할 단계 초평면 투영 방식으로 데이터 공간 분할. 기존 연구(PL-Index, AppCSE)에서 사용하는 k-means 기반의 분할 방식과 비교하여 스카이라인 계산에 유리하게 분할됨. Steps of AdaptCS 스카이라인단계 분할 단계 계층 생성 단계 X2 vTHRES a b subregion0 c d subregion1 e O X1 subregion2

AdaptCS: Adaptive Convex Skyline (cont.) 분할 단계 초평면 투영 방식으로 데이터 공간 분할. 기존 연구(PL-Index, AppCSE)에서 사용하는 k-means 기반의 분할 방식과 비교하여 스카이라인 계산에 유리하게 분할됨. Steps of AdaptCS 스카이라인단계 분할 단계 계층 생성 단계

AdaptCS: Adaptive Convex Skyline (cont.) 계층 생성 단계 각 분할된 영역에서 UB-Layer를 구축하여 지역-AdaptCS를 구함. 정확도 향상을 위하여 가상의 점 vBASE[AppCSE], vREF[AppCSE], vMAX+[PL-Index]를 사용. 지역-AdaptCS를 병합하여 최종 계층을 생성함. Steps of AdaptCS 스카이라인단계 분할 단계 계층 생성 단계 X2 vTHRES a b c d e O X1

AdaptCS: Adaptive Convex Skyline (cont.) 계층 생성 단계 각 분할된 영역에서 UB-Layer를 구축하여 지역-AdaptCS를 구함. 정확도 향상을 위하여 가상의 점 vBASE[AppCSE], vREF[AppCSE], vMAX+[PL-Index]를 사용. 지역-AdaptCS를 병합하여 최종 계층을 생성함. Steps of AdaptCS 스카이라인단계 분할 단계 계층 생성 단계 vREF X2 vBASE vMAX+ vTHRES a subregion0 b c Target T = {a, b} ∪ {d, e} ∪ vMAX+ AdaptCS0(T)= {a, b} d vREF vBASE e vREF O X1

AdaptCS: Adaptive Convex Skyline (cont.) 계층 생성 단계 각 분할된 영역에서 UB-Layer를 구축하여 지역-AdaptCS를 구함. 정확도 향상을 위하여 가상의 점 vBASE[AppCSE], vREF[AppCSE], vMAX+[PL-Index]를 사용. 지역-AdaptCS를 병합하여 최종 계층을 생성함. Steps of AdaptCS 스카이라인단계 분할 단계 계층 생성 단계 vREF X2 vBASE vMAX+ vTHRES a b c Target T = {c, d} ∪ {a, e} ∪ vMAX+ AdaptCS1(T)= {d} d subregion1 vBASE e vREF O X1

AdaptCS: Adaptive Convex Skyline (cont.) 계층 생성 단계 각 분할된 영역에서 UB-Layer를 구축하여 지역-AdaptCS를 구함. 정확도 향상을 위하여 가상의 점 vBASE[AppCSE], vREF[AppCSE], vMAX+[PL-Index]를 사용. 지역-AdaptCS를 병합하여 최종 계층을 생성함. Steps of AdaptCS 스카이라인단계 분할 단계 계층 생성 단계 vREF vBASE vMAX+ X2 vTHRES a b c Target T = {e} ∪ {a, d} ∪ vMAX+ AdaptCS2(T)= {e} d vREF e O X1 subregion2

AdaptCS: Adaptive Convex Skyline (cont.) 계층 생성 단계 각 분할된 영역에서 UB-Layer를 구축하여 지역-AdaptCS를 구함. 정확도 향상을 위하여 가상의 점 vBASE[AppCSE], vREF[AppCSE], vMAX+[PL-Index]를 사용. 지역-AdaptCS를 병합하여 최종 계층을 생성함. Steps of AdaptCS 스카이라인단계 분할 단계 계층 생성 단계 X2 a b AdaptCS = {a, b, d, e} d e O X1

UB-Layer: UnBalanced Layer Overview 차원을 분할하여 컨벡스 홀을 생성 후 병합하여 새로운 개념의 최종 계층을 구축하는 방법 고차원에서도 빠르게 색인을 구성 가능 기존 연구보다 많은 전체 계층의 수로 효율적인 질의 처리 가능 Step1 : 차원 분할 단계 데이터의 차원을 분할함 Step2 : 분할-컨벡스홀 생성 단계 분할된 차원의 데이터에서 분할-컨벡스홀을 생성함 Step3 : 병합 단계 각 분할-컨벡스홀을 병합하여 최종 계층을 구축함

UB-Layer: UnBalanced Layer (cont.) 가장 바깥의 계층이 내부의 데이터를 전부 포함하지 않는 불균형 형태 전체 계층의 수 증가 1st layer 1st layer 2nd layer 2nd layer 3rd layer Balanced Layer UnBalanced Layer

UB-Layer: UnBalanced Layer (cont.) 차원 분할 단계 입력된 데이터의 차원을 분할. Basic Algorithm : 차원을 2개로 분할함. (6차원 3차원, 3차원 / 7차원 3차원, 4차원) id value p1 <45, 25, 83, 44> p2 <50, 88, 69, 57> p3 <30, 7, 46, 60> p4 <19, 3, 28, 58, > p5 <84, 16, 50, 86> p6 <55, 30, 53, 77> p7 <39, 40, 20, 79> id value p1 <45, 25>, <83, 44> p2 <50, 88>, <69, 57> p3 <30, 7>, <46, 60> p4 <19, 3>, <28, 58> p5 <84, 16>, <50, 86> p6 <55, 30>, <53, 77> p7 <39, 40>, <20, 79> Ex) 4차원 데이터를 2차원, 2차원으로 분할

UB-Layer: UnBalanced Layer (cont.) 입력된 데이터의 차원을 분할. Select Attribute Algorithm : 주요 속성을 중심으로 차원을 분할함. 사용자가 중요하게 생각할 가능성이 높은 속성을 히스토그램으로 분석하여 해당 속성을 중심으로 차원을 분할하는 방법. id value <X1, X2, X3, X4, X5, X6> p1 <44, 30, 83, 44, 23, 45> p2 <86, 66, 69, 57, 65, 50> p3 <30, 7, 46, 60, 26, 79> p4 <19, 3, 28, 58, 49, 20> p5 <72, 16, 50, 86, 7, 88> p6 <55, 30, 53, 77, 30, 82> p7 <39, 40, 20, 79, 36, 46> id value <X1, X3>, <X2, X4, X5, X6> p1 <44, 83>, <30, 44, 23, 45> p2 <86, 69>, <66, 57, 65, 50> p3 <30, 46>, <7, 60, 26, 79> p4 <19, 28>, <3, 58, 49, 20> p5 <72, 50>, <16, 86, 7, 88> p6 <55, 30>, <53, 77, 30, 82> p7 <39, 40>, <20, 79, 36, 46> Ex) 6차원 데이터를 2차원, 4차원으로 분할

UB-Layer: UnBalanced Layer (cont.) 입력된 데이터의 차원을 분할. Hierarchical Algorithm : 계층적으로 차원을 분할함. 계층적으로 차원을 분할하여 색인 구성 시간의 감소를 극대화 시킴 id value <X1, X2, X3, X4, X5, X6> p1 <44, 30, 83, 44, 23, 45> p2 <86, 66, 69, 57, 65, 50> p3 <30, 7, 46, 60, 26, 79> p4 <19, 3, 28, 58, 49, 20> p5 <72, 16, 50, 86, 7, 88> p6 <55, 30, 53, 77, 30, 82> p7 <39, 40, 20, 79, 36, 46> id value <X1, X3>, <X2, X4, X5, X6> p1 <44, 83>, <30, 44, 23, 45> p2 <86, 69>, <66, 57, 65, 50> p3 <30, 46>, <7, 60, 26, 79> p4 <19, 28>, <3, 58, 49, 20> p5 <72, 50>, <16, 86, 7, 88> p6 <55, 30>, <53, 77, 30, 82> p7 <39, 40>, <20, 79, 36, 46> id value <X1, X3>, <X2, X4>, <X5, X6> p1 <44, 83>, <30, 44>, <23, 45> p2 <86, 69>, <66, 57>, <65, 50> p3 <30, 46>, <7, 60>, <26, 79> p4 <19, 28>, <3, 58>, <49, 20> p5 <72, 50>, <16, 86>, <7, 88> p6 <55, 30>, <53, 77>, <30, 82> p7 <39, 40>, <20, 79>, <36, 46> Ex) 6차원 데이터를 2차원, 4차원으로 분할한 후, 4차원에 대하여 다시 2차원, 2차원으로 분할

UB-Layer: UnBalanced Layer (cont.) 분할-컨벡스홀 생성 단계 분할된 차원의 데이터에 대하여 분할-컨벡스홀을 생성함. 첫 번째 나눠진 차원 데이터 div1 두 번째 나눠진 차원 데이터 div2 p2 p5 p7 p6 p3 p4 p2 p7 p1 p6 p1 p3 p5 p4 div1-CH[1] = {p2, p4, p5} div1-CH[2] = {p3, p6, p7} div1-CH[3] = {p1} div2-CH[1] = {p1, p4, p5, p7} div2-CH[2] = {p2, p3, p6}

UB-Layer: UnBalanced Layer (cont.) 병합 단계 분할-컨벡스홀을 병합하여 최종 계층을 구축함. 분할된 차원 별 계층을 중복을 제거하며 병합함 p2 p5 p7 p6 p3 p4 p2 p7 p1 p6 p1 p3 p5 p4 div1-CH[1] = {p2, p4, p5} div2-CH[1] = {p1, p4, p5, p7} ∪ ＝ UB-Layer[1] = {p1, p2, p4, p5, p7}

UB-Layer: UnBalanced Layer (cont.) 병합 단계 분할-컨벡스홀을 병합하여 최종 계층을 구축함. Basic Algorithm : 분할된 차원 별 계층을 중복을 제거하며 병합함 p2 p5 p7 p6 p3 p4 p2 p7 p1 p6 p1 p3 p5 p4 div1-CH[2] = {p3, p6, p7} div2-CH[2] = {p2, p3, p6} UB-Layer[1] = {p1, p2, p4, p5, p7 } ∪ － ＝ UB-Layer[2] = {p3, p6}

UB-Layer: UnBalanced Layer (cont.) 병합 단계 분할-컨벡스홀을 병합하여 최종 계층을 구축함. Basic Algorithm : 분할된 차원 별 계층을 중복을 제거하며 병합함 p2 p5 p7 p6 p3 p4 p2 p7 p1 p6 p1 p3 p5 p4 div1-CH[3] = {p1} UB-Layer[1] = {p1, p2, p4, p5, p7 } UB-Layer[2] = {p3, p6} － ＝ UB-Layer[3] = {}

UB-Layer: UnBalanced Layer (cont.) 병합 단계 분할-컨벡스홀을 병합하여 최종 계층을 구축함. Basic Algorithm : 분할된 차원 별 계층을 중복을 제거하며 병합함 id value <X1, X2, X3, X4, X5, X6> p1 <44, 30, 83, 44, 23, 45> p2 <86, 66, 69, 57, 65, 50> p3 <30, 7, 46, 60, 26, 79> p4 <19, 3, 28, 58, 49, 20> p5 <72, 16, 50, 86, 7, 88> p6 <55, 30, 53, 77, 30, 82> p7 <39, 40, 20, 79, 36, 46> UB-Layer[1] = {p1, p2, p4, p5, p7 } UB-Layer[2] = {p3, p6}

UB-Layer: UnBalanced Layer (cont.) 구축 결과 컨벡스 홀과는 다른 새로운 개념의 불균형 계층이 구축됨. 일부 데이터는 사용자가 원하는 순으로 계층이 구축되지 않음. 질의 처리시 계층을 더 읽으면 원하는 답을 얻을 수 있음. UB-Layer[2] UB-Layer[3] UB-Layer[1]

Performance Evaluation : AdaptCS Experimental data and environment AdaptCS와 AppCSE, Convex Skyline을 비교 Compare the following factors The index building time precision 𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛= 𝑁𝑢𝑚𝑜𝑓𝐷𝑎𝑡𝑎 𝐴𝑑𝑎𝑝𝑡𝐶𝑆 또는 𝑁𝑢𝑚𝑜𝑓𝐷𝑎𝑡𝑎(𝐴𝑝𝑝𝐶𝑆𝐸) 𝑁𝑢𝑚𝑜𝑓𝐷𝑎𝑡𝑎(𝐶𝑆) ×100 Synthetic Data Uniform distribution 10K, 2-8차원 데이터 Real Data 버지니아주의 당뇨병 환자 데이터 2-6차원 데이터 Intel i5-760 quad core processor running at 2.80GHz Linux PC with 16GB main memory C++

Performance Evaluation : AdaptCS (cont.) Result of the experiment Experiment 1. 차원 d가 변화할 때의 색인 생성 시간 비교. [Index building time] improves 0.96~1.84 times over the AppCSE and Convex skyline as d is varied. (a) Index building time as d is varied from 2-8 (b) Index building time as d is varied from 2-5 (log-scale)

Performance Evaluation : AdaptCS (cont.) Result of the experiment Experiment 2. 차원 d가 변화할 때의 데이터 분할 단계 시간 비교. [Partitioning step time] improves 1~300 times over the AppCSE as d is varied. (a) Partitioning step time as d is varied from 2-8

Performance Evaluation : AdaptCS (cont.) Result of the experiment Experiment 3. 차원 d가 변화할 때의 정확률 비교. [Precision] improves 1.1 times over the AppCSE as d is varied. (a) Precision as d is varied from 2-8

Performance Evaluation : AdaptCS (cont.) Result of the experiment Experiment 4. 한계점 단계가 변화할 때의 색인 생성 시간 및 정확률 비교. [Index building time] (a) improves 1.5 times over the AppCSE as threshold level is 4 and 5. [Precision] (b) over 90%, 98% as threshold level is 4 and 5. (a) Index building time as threshold level is varied (b) Precision as threshold level is varied

Performance Evaluation : AdaptCS (cont.) Result of the experiment Experiment 5. 실 데이터 기반 차원 d가 변화할 때의 색인 생성 시간 비교. [Index building time] improves 1.71~3 times over the AppCSE as d is varied. (a) Index building time as d is varied from 2-6

Performance Evaluation : UB-Layer Experimental data and environment Convex hull과 UB-Layer(UB-Basic, UB-SA, UB-Hier)를 비교 Compare the following factors The index building time The number of the whole layer precision 𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛= 𝑁𝑢𝑚𝑜𝑓𝐷𝑎𝑡𝑎 𝐶𝐻 − 𝑁𝑢𝑚𝑜𝑓𝐷𝑎𝑡𝑎(𝑈𝐵−𝐿𝑎𝑦𝑒𝑟) 𝑁𝑢𝑚𝑜𝑓𝐷𝑎𝑡𝑎(𝐶𝐻) ×100 Synthetic Data Uniform distribution 200, 10K, 4-12차원 데이터 Intel i5-760 quad core processor running at 2.80GHz Linux PC with 16GB main memory C++

Performance Evaluation : UB-Layer (cont.) Result of the experiment Experiment 6. 차원 d가 변화할 때의 색인 생성 시간 비교. (N=10K) (a) Index building time as d is varied from 4-8 (b) Index building time as d is varied from 4-8 (log-scale) [Index building time] improves 0.74~99.35 times over the Convex hull as d is varied.

Performance Evaluation : UB-Layer (cont.) Result of the experiment Experiment 7. 차원 d가 변화할 때의 전체 계층의 수 비교. (N=10K) [The number of the whole layer] improves 4.2~11 times over the Convex hull as d is varied. 전체 계층의 수가 증가하여, 하나의 계층의 적은 데이터를 포함하므로 효율적인 질의 처리 가능 (a) The number of layers as d is varied from 4-8

Performance Evaluation : UB-Layer (cont.) Result of the experiment Experiment 8. 차원 d가 변화할 때의 UB-Layer 방법들의 색인 생성 시간 비교. (N=10K) (a) Index building time as d is varied from 4-12 (b) Index building time as d is varied from 4-12 (log-scale) [Index building time] UB-Basic : UB-Layer 방법들 중 고차원으로 갈 수록 색인 생성시간이 느림 UB-SA : 분할 방법에 따라 차이를 보임. (<a, b> : 주어진 차원을 a차원, b차원으로 분할함) UB-Hier : 계층적으로 차원을 분할하기 때문에 고차원으로 가도 유사한 속도를 가짐

Performance Evaluation : UB-Layer (cont.) Result of the experiment Experiment 9. 차원 d가 변화할 때의 전체 계층의 수 비교. (N=10K) [The number of the whole layer] UB-Hier가 평균 2배 정도 계층의 수가 많음 (a) The number of layers as d is varied from 4-12

Performance Evaluation : UB-Layer (cont.) Result of the experiment Experiment 10. 차원 d가 변화할 때의 전체 방법들 비교. (N=10K) (a) Index building time as d is varied from 6-8 (b) Index building time as d is varied from 6-8 (log-scale) [Index building time] improves 34~2,600 times over the Convex hull as d is varied. UB-Basic improves 2600 times, UB-SA improves 800 times, UB-Hier improves 2118 times as d is 8. 고차원으로 갈 수록 향상되는 정도가 커짐.

Performance Evaluation : UB-Layer (cont.) Result of the experiment Experiment 11. 차원 d가 변화할 때의 색인 생성 시간 비교. (a) The number of layers as d is varied from 6-8 (b) Precision as d is varied from 6-8 (log-scale) [The number of the whole layer] improves 3.6~27.4 times over the Convex hull as d is varied. [Precision] 20~56 as d is varied. 차원이 증가할수록 정확도는 높아짐

Performance Evaluation : UB-Layer (cont.) Result of the experiment Experiment 12. 확장성 실험: 차원 d가 변화할 때 색인 생성 시간 비교. (N=200) (a) Index building time as d is varied from 4-10 (b) Index building time as d is varied from 4-10 (log-scale) [Index building time] improves 2~38,712 times over the Convex hull as d is varied. UB-Basic improves 900 times, UB-SA improves 365 times, UB-Hier improves 6,074 times on average. 고차원으로 갈 수록 향상되는 정도가 커짐.

Performance Evaluation : UB-Layer (cont.) Result of the experiment Experiment 13. 확장성 실험: 차원 d가 변화할 때 색인 생성 시간 비교. (N=200) (a) The number of layers as d is varied from 4-10 (b) Precision as d is varied from 6-8 (log-scale) [The number of the whole layer] improves 2~4 times over the Convex hull as d is varied. [Precision] 57~100 as d is varied. 차원이 증가할수록 정확도는 높아짐

Conclusion 고차원 대용량 데이터를 위한 계층 기반의 색인 구성 방법 제안 제안1: 한 방향의 질의 처리가 가능한 AdaptCS 정확도와 색인 구성 시간의 조절이 가능 계층에 기존 연구의 데이터를 포함하므로 질의 처리 시 정확도 보장 색인 생성 시간은 1~3배 빠르며, 정확도는 60~98%로 조절 가능 제안2: 모든 방향의 질의 처리가 가능한 UB-Layer 고차원을 위한 새로운 개념의 불균형 계층 8차원 이상에서도 색인 생성이 가능하며, 고차원에서 34~2,000배 빨라짐 첫 번째 계층 비교 시 정확도는 낮으나, 차원이 높아질수록 정확도가 높아짐  고차원을 위한 계층적 방법 향후 연구 정확도 향상 연구 구축된 색인으로 질의 처리 실험

Thank You