Spatial Keyword(SK) search query

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-k kNN Query (TkQ)

1. A query location

2. A set of keywords

3. Ranking criteria(그림에서는 2개만)

 

아래는 빨간점 위치에서 원하는 keyword를 가지는 object 중

가장 가까운 2개의 object를 select하는 것

** 키워드가 여러개일 때, 한개만 포함되어도 됨

만약 텍스트파트에 더 중요도를 주면

→ somerset mall - adidas retails 순위로 표시될 수 있고

거리에 더 중요도를 주면 

→ adidas retails- somerset mall  순위로 표시됨

 

 

 

Ranking function

아래와 같이 주어졌을 때, ranking function

ranking function에서 빨간영역은 spatial proximity

파란영역은 text relevancy를 뜻함

 

빨간색: 0~1사이의 범위값

빨간색 분자는 Euclidean distance를 뜻함

분모를 maxD로 나눠주는 것은 generalize시키기 위함으로

해당 공간에서 나올 수 있는 최대의 거리(maxD)로 나눠주는 것임

* 1일 수록 두점의 거리는 먼 것임

 

파란색: 0~1사이의 범위값

분자: keyword가 생성된 문서와 keyword의 relevency를 보는 것(=textual relevancy)

→ cosine similarity를 주로 사용

* 1일 수록 smilarity가 높음을 의미함 ( 그래서 1에서 뺀 값을 사용함 )

 

 

Boolean kNN Query

k의 개의 이웃 중 원하는 키워드를 모두 다 포함하는 object 를 찾는 것

 

 

 

위와 같은 spatial keyword search query를 위해 필요한 index

(Top-k kNN Query (TkQ)은 지원하지 않음)

- R*-IF Index = R*-tree - Inverted File

- IF-R* Index: 각각의 keyword별로 R*-tree를 built함

 

 

1. R*-IF Index

R*-tree를 built(c)한 뒤, 각 leaf node에 inverted file(b)을 추가한 구조임

inverted file: text components를 indexing 하는 것임

 

(c), (b) 두 개를 합치면 아래와 같이 표현할 수 있음

 

 

 

2. IF-R* Index

각각의 keyword에 해당하는 R*-tree가 built됨

IF-R* Index에서 Boolean 질의 처리를 하는 경우,

keyword가 italian과 expensive인 경우 두개의 tree에서 공통된 object만 추출함

 

 

 

Summary : R*-IF & IF-R* 

- BkQ, BRQ만 지원함

- BRQ에서는 IF-R* 가 더 성능이 좋음

- BkQ에서는 둘다 비슷하게 성능을 냄

 

 

 

 

IR2-Tree: 위의 두 index보다 더 개선된 형태

각 노드에 unique한 keyword에 해당하는 bitmap이 달려있음

상위 노드는 하위노드간의 or관계로 bitmap을 채움

 

 

IR2-Tree 예시)

1) 찾아야 되는 keyword와 root node의 bitmap을 and조건으로 계산한 뒤,

왼쪽으로 내려가는 것을 정함

2) Queue에 검색해야될 노드를 넣어주고 각 노드별 거리에 따라 검색순서를 정함

 

 

IR2-tree 특징

- IR2-tree는 BkQ와 BRQ에 사용될 수 있음

- TkQ에는 사용되지 않음