Download presentation
Presentation is loading. Please wait.
1
Aggregated K-nearest neighbor queries for High – dimensional data Eojin Yun, Dept. of Computer Science and Engineering, POSTECH. Motivation 만약 당신이 온라인 쇼핑몰을 운영함에 있어 서 고객이 원하는 Wish List들을 정확하고 신속하게 관리, 추천할 수 있다면 어떨까? 가능하기만 하다면 그 보다 좋은 일은 없지 않을까? 언뜻 불가능해 보이는 이 과업에 대한 청사진을 나는 이번 과제 연구를 통해서 제시하 고자 한다. Problem Statement 어떠한 상품을 단순히 Cool! Or Bad로 이분하는 것은 불가능하다 -> 오히려 각각의 상품은 개인의 성향에 따라 수많은 기준으로 분류 된다. 만약 이러한 기준을 일반화해 각각의 속성에 적용할 수 있다면? -> 그 각각의 속성은 일정한 숫자로 나타내어질 수 있을 것이고 그 기준을 하나의 축으로 생각한다면 하나의 상품은 하나의 High dimensional data 로 나타낼 수 있다. 그 동안 사용자가 구매한 물품(Query)을 토대로 그것과 비슷한 상품(비슷한 좌표의 K-nearest neighbor)를 얻을 수 있다. 그렇게 얻어진 각각의 Query에 대한 KNN의 Aggregation을 통해 최종적인 Wish List(Aggregated K-nearest neighbor)를 얻을 수 있다. ISSUES ON PROBLEM 어떻게 하면 정확하고 효율적으로 K-nearest neighbor를 구할 수 있는가? 그렇게 만들어진 각각의 Query에 대한 KNN을 어떻게 Aggregation할 것인가? SCHEME ANALYSIS Threshold Algorithm Idistance Indexing Data set p_i : (x0,x1, …, xd-1) Reference set O_i : (x0,x1, …, xd-1) Partition I * c+dist(p,Oi) Samsung SDI POSCO SK Telecom KEPCO Reference point를 기준으로 data set을 partition으로 분류 나누어진 파티션은 reference point까지의 거리에 따라 1차원 공간으로 B+ tree KNN Search ThresHold Performance List의 개수와 object의 개수와 상관 없이 TA알고리즘은 constant에 가까운 효율을 보장한다. 그러나 RA를 위한 Hash table making time은 리스트의 개수가 늘어날수록 크게 증가한다.
Similar presentations
