Spatial Access Methods 1 - Space-Driven Structure

Spatial Access Methods 1

: spatial data를 위한 indexing 기법

Spatial data에 indexing 이 필요한 이유

data가 방대하고 무거워 indexing이 필요함

컴퓨팅 시간 및 disk I/O를 최소화 할 수 있음

indexing 효과

데이터가 커지더라도 n개의 데이터에 대해 log(N)의 시간을 기대할 수 있음

 

 

 

각 타입에 최적화된 indexing이 따로 있음

points, lines, and polygons타입별 사용 indexing이 있음 (oid)

모든 것을 다 커버하는 general 한 indexing이 있음 (mbb)

eg) minimum bounding box (mbb), minimum bounding rectangle(mbr)

entry를 나타낼 때는 [mbb, oid]의 쌍으로 표현함

** oid는 disk주소를 의미하고

   그 안에는 상세한 정보(attribute)까지 다 가지고 있는 indexing 방법임

mbr의 2가지 장점

1. 복잡한 모양의 geometric도 단순화 시켜서 표현하므로 비용절약

2. mbr을 활용하면 특정 shape에 근사한 shape(rectangle)정보만 필요함

   (constant-size: 2개의 꼭지점)

    즉, mbb, mbr의 사각형은 양 변의 2개의 꼭지점만 표현하면 됨

 

mbb에서 indexing 하는 2가지 step

• filter step : 특정 조건(spatial predicate)에 만족하는 mbb를 추출해냄

• refinement step : 필터 스텝을 통과하는 것중에 query prediate를 만족하는 것을 찾아냄

여기서 검은동그라미는 filter step단계는 통과하지만 refinement step은 통과할 수 없음

이런 검은 동그라미를 false drop이라 함

 

 

B+-trees

• 기본 전통적인 DBMS에서 사용되는 indexing methods 방법
• 위의 방법은 n개의 데이터에 대해 log(N)의 I/O 접근을 보장함
• 단점, spatial indexing이 불가능함 ( 좌표데이터 등)

→ 왜냐하면 index값이 정렬(순서)이 가능해야함

    (정렬이 가능한 data를 “total order”라고 함)

 

 

위 와 같은 좌표데이터에서 B, C점의 크기 비교는 불가능 함

spatial data에서 사용하는 2가지 indexing 기법

1. Grid
2. R-tree

위의 두 방법의 특징

간단하다.

robust하다

좋은 index를 평가하는 방법(index를 생성해야할 때 고려해야 할 것)

• index construction time

        index 빌드할 때 얼마나 걸리는지

• search operation time

       질의 처리 할 때 얼마나 걸리는지

indexing 할때 가정하는 5가지(그러므로 indexing이 필요함)

1. main메모리보다 훨씬 더 큰 데이터가 존재함

2. disk 접근 시간은 메인 메모리 접근시간보다 훨씬 크다

3. 메모리와 디스크 사이의 데이터 이동은 page단위로 발생함

      (I/O는 disk page단위로 처리됨. 즉, page에 있는 데이터 한개만 가져오는 것과, 

      같은 page에 있는 데이터 10개를 가져오는것의 I/O는 같음)

       page size는 1K~4K로 가정

 

4. CPU time은 무시

5. caching에 미리 가져오는 것은 성능 평가에 고려하지 않음

 

 

좋은 indexing이 만족시켜야 하는 요건

1. Time complexity: 주어진 시간목적에 만족해야함

2. Space complexity: index크기는 page수에 비례하여 증가해야함(제곱으로 늘어나면 안됨)

3. Dynamicity: 삽입과 삭제에 대해 유연해야함

Space-Driven Structures SAM 

에서 대표적인 index: Grid file indexing 기법

공간을 격자의 모양으로 쪼개서 처리함

초기에 사용되었던 indexing 기법

Data-Driven SAMs

에서 대표적인 index: R-tree, R*-tree R+tree indexing 기법

Organized by partitioning the set of objects

(공간에 embedding되어있는 object들을 grouping 하는 방식)

Space-Driven Structure

[Fixed grid] : 가장 기초적인 index 기법 for spatial data

The fixed grid ( Grid file indexing 기법 )

16개의 셀에 대응되는 2차원 배열을 사용함

2차원 배열은 disk주소를 가짐

 

1. 여기서는 수식을 사용하는데 공간의 가장 기본이 되는 좌표를 사용함 (x0, y0)

2. 배열의 표현은 1부터 nx, 1: ny로 표현할 수 있음 (여기서 Nx, Ny=4)

    → DIR[i,j]가 나타내는 것은 pageID이며, 각 page ID에는 특정 point들이 저장되어 있음

3. [Sx, Sy]일 때 각 사이즈의 크기는 [Sx/nx, Sy/ny]로 표현할 수 있음

‘

Inserting P(a, b): 수식 정의

point(a,b)가 DIR[i, j]으로 표현되는 것

즉, 배열로 inserting 하는 것

 

위의 그림 에서 

• Sx = 50
• Sy= 40
• (x0, y0) = (0,0 )
• nx = 5
• ny = 4

 

점 p(35, 25)일 때

• i = (35 - 0) /10 +1 = 4.5
• j = (25 - 0) /10 +1 = 3.5

그러므로 대략 (4, 3)의 배열로 저장된다고 할 수 있음

Window query

특정영역(window) (i1, j1) 부터 i2, j2에 해당하는 점 9개를 찾아 주는 것 (filter step)

해당되는 점 9개를 원하는 질의에 맞게 처리하는 것이 refinement step임

The fixed grid 에서

장점: point query를 효율적으로 수행할 수 있음(간단함)

특징1. windown query에서 # I/O는 # of cell에 비례함

특징2. 각 셀은 수용할 수 있는 point에 제한이 있음

→ 초과하면 overflow 발생 

 

 

overflow 발생 시 처리 방법

M=4 즉, 한개의 셀에 들어가는 point의 max값이 4일 때

5번째 점이 들어올 경우, 해당 셀에 linked 된 overflow page가 생성되어 저장됨

overflow 처리 시 단점

disk I/O가 추가로 발생됨

즉, 성능이 일정하지 않음

(왜냐하면 chain에 link되어 있는 경우와 안된 경우 읽는 속도가 달라지므로)

→ 따라서, uniform하게 point가 분포되어있는 경우는 overflow를 사용해도 됨

→ 단, 특정지역에 왕창 몰려있으면 안 좋음 (fixed grid 방식 자체가 좋지 않음)

[The grid file]

The grid file: Fixed grid보다 더 좋은 방법임

(간격이 유연함)

 

기존에 사용했던 수식을 사용할 수 없음

 

Sx =  

1	2	3	4	5
10	40	45	inf.

 

Sy =  

1	2	3	4	5
5	20	inf.	…

 

각 grid가 쪼개진 위치값을 가지고 있음

P가 (25, 48)일 때 

i = 3(25<40: 3번째), j=4(48<60: 4번째) 임 

 

각 좌표계가 분할 되는 경우, Sx, Sy가 가질 수 있는 배열의 변화

3번단계에서 Sx, Sy의 배열은 아래와 같이 되므로 총 2x2 배열임

• Sx [x1, inf.]
• Sy [y1, inf.] 

 

2번단계에서 Sx, Sy의 배열은 아래와 같음

• Sx [x1, inf.]
• Sy [inf.] 

 

2번에서 3번으로 변화 시 directory split

3번에서 점f, c가 추가가 됐을 때는 cell split

fixed grid에서 처럼 overflow발생이 없도록 각 셀에 4개를 초과하는 점이 들어오게 되면

directory split을 할 수 있음

최대한 각 영역에 균일한 point들이 들어올 수 있도록 split하는 방법임

 

 

 

 

point가 아닌 rectangle일 때의 The Grid File

 

rectangle 14가 추가 되면서 Directory split 발생

[14가 추가되기 전]

[14가 추가된 후]

 

point P를 포함하고 있는 page를 return하는 것

(Point query algorithm with the grid file)

i, j의 좌표값을 통해 page id를 return하고

그 page id의 mbb(minimum bounding box)내에 속하면 result에 추가하는 것

eg) point 8을 포함하고 있는 page를 return하는 것

점 P는 8mbb에 속해있는 점임을 알 수 있음

Window query algorithm with grid file

 

 

예를 들어, (i1, j1) = (2,4) , (i2=6, j2=10) 이면

2<= x <=6, 4<=y <=10 이므로

[ 2, 3, 4, 5, 6 ]과 [4,5,6,7,8,9,10]의 모든 조합에 대해 page id를 받아옴

 

단점 1. sort후 중복을 제거하기 때문에 계산이 복잡

단점 2. 셀이 작아질 수록 모든 조합을 봐야되므로  복잡함

→ Impossible for very large data sets