[파일 처리] 10 다차원 공간 화일

1. 다차원 공간 화일

1) 특징

- 여러 개의 필드를 동시에 키로 사용한 화일

 

2) 종류

- PAM(Point Access Method) : 다차원의 점 데이터를 저장, 검색

- SAM(Spatial Access Method) : 선, 면과 같은 다차원 도형 데이터를 저장, 검색

 

2. k-d 트리

1) 개념

- 이원 탐색 트리를 다차원 공간으로 활장한 것

- 기본 구조와 알고리즘은 이원 탐색 트리와 유사

- 트리의 레벨에 따라 차원을 번갈아 가며 비교

 

2) 특징

- 주기억 장치 상에서 동작

- 소규모의 다차원 점데이터를 인덱싱 할 때 적합

- 균형 트리가 아님

 

3) 삽입

- 4사분면에서 루트 점 저장하고 x값과 y값을 번갈아가며 비교하며 자식 노드에 삽입한다.

 

4) 단점 : 균형트리가 아니므로 검색 성능이 떨어짐

 

3. k-d-B 트리

1) 특징

- B트리와 k-d 트리와 결헙 : 디스크 기반, 다차원 점 데이터 저장,검색, 완전균형트리

 

2) 구조

- 다중 키 레코드 검색을 위한 인덱스 레코드 : (키0, 키1, ..., 키k-1, 주소)

- 점 : 도메인0*도메인1*...도메인k-1의 한 원소

- 영역 : 같은 성질을 가지고 있는 점들의 집합

- 노드는 루트 페이지와 페이지의 집합

 

3) 특성

- 각 페이지를 노드로 갖고, 페이지 id를 노드 포인터로 갖는 다원 탐색 트리

- 모든 단말 페이지까지의 경로 길이는 동일

- 모든 영역은 분리

- 루트 페이지가 영역 페이지면, 영역들의 합은 영역 전체

 

 

4. 격자 화일

1) 개념 : 전체 공간을 하나 이상의 격자로 분할 – 데이터 추가에 따라 기존 격자를 분할하여 새로운 격자 구성

 

2) 특징

– 디스크 기반 : 대용량 데이터 처리

– 해시 기반 : 일반적으로 두 번의 디스크 접근으로 데이터 검색

 

3) 구성 

> d차원의 격자 화일 – 격자 디렉토리(grid directory)

- d개의 선형 눈금자 : 격자 디렉토리를 구성하는 각 차원별 눈금 정보, 주기억 장치에 유지

- d차원의 격자 배열(grid array) : 선형 눈금자에 의해 분할된 격자, 하나 이상의 격자 블록으로 구성, 디스크에 저장

 

> 데이터 페이지

- 실제 데이터가 저장되는 장소

- 디스크에 저장 

 

> 격자 블록과 데이터 페이지

– 기본적으로 하나의 격자 블록당 하나의 데이터 페이지

– 두 개 이상의 격자 블록이 하나의 데이터 페이지 공유 가능

4) 격자 화일의 장단점

- 격자 화일은 인덱스의 각 키들이 균등하게 분포되어 있을 때 효율적 

- 페이지 오버플로우로 인해 격자를 분할할 때 격자의 수가 불필요하게 증가

- 격자의 합병 비용이 많이 듦

 

5. 사분 트리

1) 개념

- 공간을 순환적으로 분해하는 계층적 자료구조

> 사분 트리의 분류 기준  :  자료의 유형, 공간 분해 과정의 원칙, 해상도(resolution)

 

> 사분 트리로 표현하는 자료의 유형

- 점(point), 영역(region), 곡선(curve), 표면(surface), 볼륨(volume)

- 개체의 경계를 표현하는 경우 : 곡선, 표면 데이타

- 개체의 내부를 표현하는 경우 : 영역, 볼륨 데이타

 

> 공간의 분해 원칙

- Image space hierarchy : 각 레벨마다 공간을 일정 크기의 동일한 부분들로 분해

- Object space hierarchy : 입력 자료 값에 따라 서로 다른 크기의 공간으로 분해

 

> 해상도

- 분해 과정을 몇 번이나 적용하느냐는 것

- 미리 일정 레벨까지만 분해하도록 고정하거나 입력 데이터의 특성에 따라 가변적으로 함

 

2) 영역 사분 트리

- 이차원 영역 데이타 표현에 많이 사용

- 이미지를 표현하는 2진수의 배열을 연속적으로 동일한 크기의 사분면들로 분할 : 가변 해상도의 자료 구조 

 

> 영역 사분 트리

- 차수가 4인 트리

- 루트 노드는 전체 배열에 대응

- 자식 노드들은 각 영역의 사분면 표현(NW, NE, SW, SE순)

- 리프 노드 : 영역의 내부 표현(1, 흑색 노드) 또는 영역의 외부 표현(0, 백색 노드)

- 단말이 아닌 노드 : 회색 노드(0과 1 모두 가짐

 

3) 점 사분 트리

- 점 데이터를 표현

- 공간을 동일하지 않은 4개의 부속 공간으로 분할

 

> 이차원 점 데이터에 대한 인덱스로 활용

- 단말 노드가 버켓의 포인터를 가진다면 인덱스 역할

- 전체 레코드는 인덱스에 의해 참조되는 버켓에 저장

 

> 다차원 데이터를 위한 이진 탐색 트리의 일반화

 

> 이차원 점 데이터 : 데이터 필드, x 좌표, y 좌표, 네 개(NW, NE, SW, SE )의 포인터 필드를 가지는 노드로 표현

 

① 삽입 : 이진 탐색 트리에 대한 삽입과 유사한 방법

* 점 사분 트리의 구축 비용 = 트리의 총 경로 길이

– 데이터 N개의 평균 삽입 비용 : O(Nlog4N)

– 한 노드의 탐색 비용 : O(log4N)

 

> 최적 점 사분 트리 구성 방법

– 모든 점 데이터들을 미리 알 수 있는 경우에 가능

– 임의 노드의 어떤 서브트리도 전체 노드 수의 반 이상을 갖지 않는 트리로 정의

– 이를 위해, 모든 점 데이타들을 하나의 좌표축(x) 값으로 정렬하고 다른 좌표축(y) 값은 보조 키로 사용

– 루트는 정렬 화일의 중간 값을 갖고, 나머지는 4개 부속 그룹으로 나누어 루트의 네 서브트리가 되도록 함

– 이 과정을 반복적으로 적용해서 트리 구성

 

② 검색 : 탐색 공간을 좁혀 나가는 기법, 범위 탐색, 근접 탐색에도 적합

 

③ 삭제 : 삭제할 노드를 루트로 하는 서브 트리에 있는 모든 노드들이 재삽입 되어야 함 => 복잡

* 이상적인 삭제 : 삭제할 노드를 다른 노드로 대체한후 삭제

 

6. R-트리

1) 개념 : B-트리를 다차원으로 확장시킨 완전 균형 트리

 

2) 특징

- 선 , 면, 도형 등 다양한 다차원 공간 데이터 저장 가능

- 루트 노드가 아닌 노드는 최소 m, 최대 M개의 엔트리를 포함

- 루트 노드는 리프가 아닌 경우 최소 2개의 엔트리를 포함

- 완전 균형 트리

- 객체는 단말 노드에서 단 한번 나타나지만 비 단말 노드를 표현하는 디렉토리 사각형은 서로 겹칠 수 있음

- 단말 노드 N 엔트리 : (oid, mbr)

- 비 단말 노드 n의 엔트리 : (p, mbr)

 

3) mbr : 복잡한 공간 도형을 저장하기 위해 mbr이용

 

✅ R트리 예시

- 밀집된 지역에는 이웃하는 단말 노드가 더 많이 생성됨

- 밀집 지역에서 노드간의 겹침 현상이 더 많이 발생

 

4) 연산

① 검색 : 리프노드가 아닌경우 하위 노드를 검사해가며 결과를 발견하면 반환한다.

* K-NN 질의 : 질의점으로부터 가장 가까운 K개의 데이터 검색

(우선순위 큐에 트리 노드 포인터 p와 질의 점과의 거리 d를 쌍으로 하는 엔트리를 저장)

큐의 우선순위는 가까울 수록 우선순위가 높으며, 루트 노드를 첫번째로 큐에 삽입

 

② 삽입 : b트리와 유사

- 리프노드 선택 : 데이터를 삽입할 리프 선택

- 리프노드에 데이터 저장 : 선택된 리프토드에 빈 공간이 있으면 새로운엔트리 e를 저장

* 빈 공간이 없는 경우 노드를 분할하고 e를 저장

- 트리 재조정

- 트리 높이 증가

 

* 리프 노드 선택 알고리즘

• n은 루트노드 t에서 시작
• n이 리프노드이면 n을 반환
• n이 리프노드가 아니면 n의 엔트리 가운데 e가 삽입되었을 경우 mbr의 크기가 가장 작게 증가하는 엔트리 f선택
• 선택된 엔트리 f가 가르키는 노드를 n으로 하여 알고리즘 2부터 반복 수행

* 트리의 분할 방법 : 분할된 두 노드 mbr의 합을 최소가 되도록 분할을 선택

-> 검색시 불필요한 노드의 탐색을 줄일 수 있음

 

③ 삭제 : b트리와 유사

- 리프노드 탐색

- 해당 엔트리 삭제

- 언더플로 처리 

 

5) R트리의 분석

- d차원의 데이터를 처리하기 위한 b트리의 확장으로서 중간 노드와 리프 노드로 구성된 높이 균형트리

- 탐색 : 포함과 겹침관계가 중요(포함과 겹침 관계가 최소 일때 가장 효율적임)

- 루트를 제외한 모든 노드에서 최악의 공간 활용도 : m/M

(트리의 높이를 감소시키면 공간활동도는 증가)