| 1 |
1
공간 데이터 객체를 수신하여 공간 블록체인에 저장하는 단계;상기 공간 데이터 객체의 지오해시(geohash)값과 상기 공간 블록체인 상의 블록 주소(blockaddress)를 기초로 해시-주소 쌍을 생성하는 단계;상기 해시-주소 쌍을 메모리 컴포넌트(memory component)에 저장하는 단계;상기 메모리 컴포넌트의 공간 점유율이 기 설정된 제1 임계값을 초과하는 경우 상기 메모리 컴포넌트에 저장된 제1 항목들을 순차적으로 디스크 컴포넌트(disk component)에 플러시(flush)하는 단계;상기 디스크 컴포넌트의 공간 점유율이 기 설정된 제2 임계값을 초과하는 경우 상기 디스크 컴포넌트에 저장된 제2 항목들을 순차적으로 하위 레벨의 디스크 컴포넌트에 플러시하는 단계; 및상기 메모리 컴포넌트 또는 상기 디스크 컴포넌트의 변경을 반영하여 컴포넌트 테이블(component table)을 갱신하는 단계를 포함하고,상기 컴포넌트 테이블은 인덱스 트리를 구성하는 컴포넌트들에 대한 정보로서 컴포넌트 레벨(component level), 블록 주소(block address), 키 범위(key range) 및 공간 필터(spatial filter)를 포함하는 것을 특징으로 하는 공간 분할 기반의 트리 인덱싱 및 질의어 처리 방법
|
| 2 |
2
제1항에 있어서,상기 컴포넌트 테이블은 상기 컴포넌트들을 상기 컴포넌트 레벨 순서대로 정렬하여 저장하고,상기 공간 필터는 해당 컴포넌트가 커버하는 영역에서 데이터가 분포하는 영역에 관한 정보를 포함하는 비트 스트링(bit string)으로 구현되는 것을 특징으로 하는 공간 분할 기반의 트리 인덱싱 및 질의어 처리 방법
|
| 3 |
3
제2항에 있어서, 상기 공간 필터는해당 컴포넌트가 커버하는 영역을 n(상기 n은 자연수)개의 셀 영역들로 분할하는 단계;상기 셀 영역들을 지오해시 순서로 정렬하는 단계;j(상기 j는 자연수)번째 셀 영역에 객체가 존재하는 경우 j번째 비트(bit)를 '1'로 표시하고 그렇지 않은 경우 '0'으로 표시하는 단계; 및모든 셀 영역에 대응되는 n개의 비트들 각각의 값을 결정하여 비트 스트링을 생성하는 단계의 순차적인 실행을 통해 생성되는 것을 특징으로 하는 공간 분할 기반의 트리 인덱싱 및 질의어 처리 방법
|
| 4 |
4
제1항에 있어서,상기 메모리 컴포넌트에 저장하는 단계는각각이 인덱스 블록(index block) 및 적어도 하나의 해시-주소 블록(geohash/address block)을 포함하는 복수의 컴포넌트(component)들 중 어느 하나에 저장하는 단계를 포함하는 것을 특징으로 하는 공간 분할 기반의 트리 인덱싱 및 질의어 처리 방법
|
| 5 |
5
제4항에 있어서,상기 인덱스 블록은 해당 컴포넌트에 저장된 해시-주소 쌍들에 대한 인덱스로서 상기 지오해시값에 관한 B+ 트리를 포함하며,상기 적어도 하나의 해시-주소 블록은 상기 해시-주소 쌍을 상기 지오해시값에 대해 정렬된 상태로 저장하는 것을 특징으로 하는 공간 분할 기반의 트리 인덱싱 및 질의어 처리 방법
|
| 6 |
6
제1항에 있어서,상기 디스크 컴포넌트에 플러시하는 단계들 각각은동일 레벨의 컴포넌트들 중에서 상기 키 범위가 같은 컴포넌트들을 하나의 컴포넌트로 병합하는 단계; 및상기 병합된 컴포넌트의 크기가 임계값을 초과하는 경우 하위 레벨의 새로운 컴포넌트를 생성하는 단계를 포함하는 것을 특징으로 하는 공간 분할 기반의 트리 인덱싱 및 질의어 처리 방법
|
| 7 |
7
제1항에 있어서,질의 포인트 및 질의 범위에 관한 범위 질의를 수신하는 단계;상기 컴포넌트 테이블을 스캔하여 상기 범위 질의에 관한 결과 집합을 생성하는 단계; 및상기 결과 집합을 상기 범위 질의에 대한 응답으로 제공하는 단계를 더 포함하는 것을 특징으로 하는 공간 분할 기반의 트리 인덱싱 및 질의어 처리 방법
|
| 8 |
8
제7항에 있어서, 상기 결과 집합을 생성하는 단계는공간 필터와 동일한 크기의 비트 스트링으로 구현되는 질의 필터를 생성하는 단계;상기 질의 필터를 이용하여 컴포넌트 테이블을 스캔하여 상기 범위 질의에 연관된 객체를 포함하는 적어도 하나의 질의 컴포넌트를 검출하는 단계; 및상기 적어도 하나의 질의 컴포넌트에 대한 인덱스를 탐색하면서 상기 범위 질의에 관한 질의 결과를 생성하여 결과 집합에 추가하는 단계를 포함하는 것을 특징으로 하는 공간 분할 기반의 트리 인덱싱 및 질의어 처리 방법
|
| 9 |
9
제8항에 있어서,상기 질의 필터를 생성하는 단계는컴포넌트 레벨 별로 상기 공간 필터의 크기에 대응되는 상기 질의 필터를 생성하는 단계를 포함하고,상기 질의 필터는 상기 질의 포인트와 상기 질의 범위에 의해 결정되는 질의 영역에 관한 정보를 포함하는 것을 특징으로 하는 공간 분할 기반의 트리 인덱싱 및 질의어 처리 방법
|
| 10 |
10
제9항에 있어서,상기 적어도 하나의 질의 컴포넌트를 검출하는 단계는특정 컴포넌트의 공간 필터와 상기 질의 필터 간의 논리곱(AND) 연산을 수행한 결과 0보다 큰 비트가 존재하는 경우 상기 특정 컴포넌트를 질의 컴포넌트로 결정하는 단계를 포함하는 것을 특징으로 하는 공간 분할 기반의 트리 인덱싱 및 질의어 처리 방법
|
| 11 |
11
제7항에 있어서,상기 결과 집합을 생성하는 단계는상기 메모리 컴포넌트를 스캔하여 상기 범위 질의와 연관되는 컴포넌트들을 후보 집합으로 생성하는 단계;상기 질의 범위를 기초로 상기 컴포넌트 테이블을 스캔하면서 상기 질의 범위를 커버하는 컴포넌트들에 대해 상기 질의 포인트와의 거리를 계산하여 우선순위 큐에 삽입하는 단계;상기 컴포넌트 테이블에 대한 스캔이 완료되면 상기 질의 포인트로부터 가장 가까운 거리를 갖는 루트 노드를 상기 우선순위 큐를 통해 선택하고 자식 노드들에 대한 탐색을 수행하는 단계;상기 탐색이 완료되면 상기 후보 집합 및 상기 질의 반경을 갱신하는 단계; 및상기 우선순위 큐를 통해 다음 노드를 선택하여 상기 탐색을 반복하는 과정에서 상기 다음 노드와 상기 질의 포인트 간의 거리가 상기 질의 반경보다 큰 경우 상기 반복을 종료하고 현재의 후보 집합을 상기 결과 집합으로 결정하는 단계를 포함하는 것을 특징으로 하는 공간 분할 기반의 트리 인덱싱 및 질의어 처리 방법
|
| 12 |
12
공간 데이터 객체를 저장하는 공간 블록체인;상기 공간 데이터 객체를 인덱싱하는 인덱스 트리; 및상기 인덱스 트리를 생성하는 인덱스 트리 생성부를 포함하고,상기 인덱스 트리는상기 공간 데이터 객체의 지오해시(geohash)값과 상기 공간 블록체인 상의 블록 주소(blockaddress)를 기초로 생성된 해시-주소 쌍을 저장하는 메모리 컴포넌트;상기 메모리 컴포넌트와 연동하여 동작하고, 상기 해시-주소 쌍을 저장하는 복수의 컴포넌트들을 레벨 별로 그룹화 하여 저장하는 디스크 컴포넌트; 및컴포넌트들에 대한 정보로서 컴포넌트 레벨(component level), 블록 주소(block address), 키 범위(key range) 및 공간 필터(spatial filter)를 저장하는 컴포넌트 테이블을 포함하는 것을 특징으로 하는 공간 분할 기반의 트리 인덱싱 및 질의어 처리 장치
|
| 13 |
13
제12항에 있어서,상기 인덱스 트리를 이용하여 상기 공간 데이터 객체에 관한 범위 질의를 처리하는 질의 처리부를 더 포함하는 것을 특징으로 하는 공간 분할 기반의 트리 인덱싱 및 질의어 처리 장치
|
