sarah0518

SNS내의 데이터를 보면, 좌표 데이터(POI: Point of Interest)와 text 데이터가 같이 올라오는 경우가 많음 이런 데이터를 분석하기 위한 기법이라 할 수 있음 : (Geo-Textual) Data Geo-Textual Data의 components - text - location - time Boolean Range Query: keyword가 존재할 때 사용하는 range query 1. A query region: 범위에 대한 질의처리 2. A set of keywords: keyword를 포함하고 있는 object를 검색하는 질의처리 범위에 대한 질의 처리 후(빨간영역), keyword에 대한 질의처리(스마일표시)를 하는 그림 ** 키워드가 여러개일 때, 모두 포함되어야함 Top..

CNN정의 CNN: Continuous에서 split points(s1, s2, s3)와 대응되는 NN을 찾는 것임 용어정리 1. split list: [s, s1, s2, s3, e] 2. vicinity circle: split point에 대응되는 원 3. cover: [a,c,f,h]들은 특정 구간에 있는 point u에 대해서 NN이기 때문에 특정 구간을 cover한다고 할 수 있음 CNN법칙 Lemma 1. - 점a가 추가 되었을 때, s까지의 거리와, e까지의 거리를 반지름으로 하는 원을 그림 - 점c가 추가되었을 때, 원e 안에 존재하므로 a와 c를 연결한 후, 수직인 선분을 그어 그점이 기존 s-e의 직선과 만나는 원의 중심인 s1이 됨 CNN 법칙 Lemma 2. Covering Con..

RNN 정의 q를 nearest neighbor로 하는 것을 찾는 것임 (p2, p3) eg) 통신회사에서 요금제를 개발했을 때, 누구에게 요금제를 광고하는 것이 효과적일까? 해당 요금제와 가장 유사한(가까운) 요금제를 쓰는 사람에게 홍보하는 것이 좋음 RNN(p2)={ } 공란임 (참고로, RNN(p3)={q}, NN(q) = p3 ) 따라서, RNN은 대칭 관계가 아님 RNN 알고리즘 개요 1. [KM00] KM method : pre-computing 1. 모든 점p1~4에 대해 NN을 찾고 2. 그 거리를 반지름으로 하는 원(vicinity circle)을 그림 3. RNN tree를 build함(MBR) 4. q가 포함된 원의 중심이 q의 RNN임 = p3, p4 * 미리 모든 P에 대한 NN을..

Road Network layer는 graph로 표현됨 * 휘어진 도로는 구간을 짧게 쪼개 직선거리로 표현함 아래 회색점이 곡선 구간을 작게 쪼갠점임 네트워크상의 두 노드의 거리 표현 방법 직접 연결 안된 두 노드의 거리는 두 노드의 최단거리로 표현한다는 의미임 네트워크 distance의 속성1 네트워크 distance의 속성2 네트워크 distance는 Euclidean distance보다 항상 크거나 같다. Euclidean distance: 최단 직선거리임 실제 도로와 그것을 네트워크 modeling으로 표현한 것 Nearest Neighbor Queries in Network DB 1. IER(Incremental Euclidean Restrictions) Algorithm : 회색영역을 점점 줄..

Spatial join 각 MBR이 겹치는 것을 찾아서 join을 하는 것임 위의 초록7개와 빨강 7개의 7*7 pair에 대해서 겹치는 것을 찾으면 됨 Join1 2개의 tree-depth가 같을 때, 사용가능함 위와 같은 logic을 따름 즉, 겹치는 E와 F가 leaf node이면 결과에 추가하고, 겹치는 E와 F가 internal node이면 다시 loop를 돌림 → 단, 연산시간이 많이 걸림 (7*7=49 pair) 개선1. Restricting the search space (Join2) 개선2. Spatial sorting and plane sweep Join2: Restricting the search space 각 pair를 다 계산하는 것을 최적화시킴 → root MBR (R, S)에서..

기존 indexing의 문제점 high dimensional data에서는 기존의 indexing 기법이 잘 적용되지 않음 비슷한 데이터의 grouping이 힘들게 됨 → 겹치는 데이터가 많아짐 → 차원의 저주 M-tree(Metric indexing) 직접 grouping하는 것이 아니라, 거리를 계산하여 거리기준으로 grouping 하는 것 (distance based indexing) 따라서 차원에 대해 independent한 indexing을 설계 할 수 있음 metric space metric space에 존재한다고 하려면 아래 조건을 만족해야함 도로망 같은 경우는 metric space의 조건을 만족하지 않음 A보다 B도로가 더 길 수 있음 M-tree 특징 차원의 저주에 dependent 하..

Range query index없이 모든 point들을 다 살펴보는것은 효율적이지 않음 반면, R-tree의 범위 질의를 통해 빠르게 query에 답할 수 있음 aggregation query: 특정 범위내에 있는 값에대해 집계처리(count, sum, avg, min, max)의 결과를 return하는 것 Straightforward approach: reduce to a range query. Better approach: along with each index entry, store aggregate of the sub-tree. 노란색 처럼 각 노드에 count 값을 미리 가지고 있음 Nearest Neighbor (NN) Query eg) Given a query location q, find ..

R-tree (Rectangle tree) 각 노드가 최소 50%이상 사용되도록 하는 트리 insert와 split이 수월하다 query수행 시 MBR을 사용한다. DISK 기반의 TREE임 (A multi-way external memory tree) 현재 가장 많이 사용하는 TREE HEIGHT(level)이 균일하므로 DISK I/0가 균일하게 발생함 하나의 노드는 최소 m개의 entry가, 최대 M개의 entry를 가지도록 제한됨 단, root 노드는 최소 2개의 entry(children)를 가질 수 있음(한개도 괜찮음) m과 M에 대한 예시 ** mbr의 grouping의 결과를 tree 구조로 나타낸 것임 ** 일부분이 걸쳐있는경우에는 포함이 안됨 (P3에 H는 포함 안됨) ** F = 4 ..