| 1 |
1
(a) 주어진 공간의 분할 방식을 결정하여 상기 주어진 공간을 복수의 서브 공간들(각각은 KD-tree의 노드를 형성함)로 분할하는 단계; 및(b) 상기 복수의 서브 공간들 각각을 상기 주어진 공간으로 설정하여 상기 단계 (a)를 반복하는 단계를 포함하고,상기 (a) 단계는 해당 서브 공간이 상기 KD-tree(K-Dimension tree)의 내부 노드에 해당하면 상기 내부 노드에 있는 원시 데이터의 개수가 임계치를 초과하는지 여부를 체크하고 상기 서브 공간(KD-tree 노드)의 상기 원시 데이터 개수를 기초로 상기 서브 공간의 분할 방식을 결정하는 단계를 포함하는 KD-tree 생성 방법
|
| 2 |
2
제1항에 있어서, 상기 임계치는상기 해당 서브 공간을 정렬 방식으로 분할할 때 요구되는 내부 메모리의 크기를 기초로 결정되는 것을 특징으로 하는 KD-tree 생성 방법
|
| 3 |
3
제1항에 있어서, 상기 내부 노드는 상기 주어진 공간의 분할 면과 분할 면에 의해 분할된 복수의 서브공간으로 구성되는 것을 특징으로 하는 KD-tree 생성 방법
|
| 4 |
4
제1항에 있어서, 상기 (a) 단계는상기 원시 데이터의 개수가 상기 임계치를 초과한다면 상기 해당 서브 공간을 비닝(binning) 방식으로 분할하여 상기 복수의 서브 공간들을 생성하는 단계를 더 포함하는 것을 특징으로 하는 KD-tree 생성 방법
|
| 5 |
5
제1항에 있어서, 상기 (a) 단계는 상기 원시 데이터의 개수가 상기 임계치를 초과하지 않는다면 상기 해당 서브 공간을 정렬(sorting) 방식으로 분할하여 복수의 서브 공간들을 생성하는 단계를 더 포함하는 것을 특징으로 하는 KD-tree 생성 방법
|
| 6 |
6
제5항에 있어서, 상기 (a) 단계는상기 해당 서브 공간에 대한 정렬 방식의 분할을 병렬적으로 수행하여 상기 복수의 서브 공간을 생성하는 단계를 포함하는 것을 특징으로 하는 KD-tree 생성 방법
|
| 7 |
7
제1항에 있어서, 상기 (a) 단계는상기 복수의 서브 공간들의 분할 순서를 상기 KD-tree의 방문 순서로 변환하여 상기 복수의 서브 공간들을 메모리에 저장하는 단계를 포함하는 것을 특징으로 하는 KD-tree 생성 방법
|
| 8 |
8
제7항에 있어서, 상기 복수의 서브 공간들을 메모리에 저장하는 단계는상기 주어진 공간의 분할을 통해 생성된 노드의 주소 및 노드의 데이터를 입력 받는 단계; 및상기 노드의 데이터가 저장될 버스트 노드 엔트리(burst node entry)의 위치를 탐색하는 단계를 포함하고,상기 버스트 노드 엔트리의 위치를 탐색하는 단계는 노드 주소와 버스트 주소를 비교하는 단계를 포함하는 것을 특징으로 하는 KD-tree 생성 방법
|
| 9 |
9
제7항에 있어서, 상기 복수의 서브 공간들을 메모리에 저장하는 단계는노드 데이터가 저장될 공간이 없는 버스트 노드 엔트리를 탐색하는 단계를 포함하는 것을 특징으로 하는 KD-tree 생성 방법
|
| 10 |
10
(a) 주어진 공간의 분할 방식을 결정하여 상기 주어진 공간을 복수의 서브 공간들(각각은 KD-tree의 노드를 형성함)로 분할하고,(b) 상기 복수의 서브 공간들 각각을 상기 주어진 공간으로 설정하여 상기 단계 (a)를 반복하는 트리 생성 유닛을 포함하고,상기 트리 생성 유닛은 해당 서브 공간이 상기 KD-tree의 내부 노드에 해당하면 상기 내부 노드에 있는 원시 데이터의 개수가 임계치를 초과하는지 여부를 체크하고 상기 서브 공간(KD-tree 노드)의 상기 원시 데이터 개수를 기초로 상기 서브 공간의 분할 방식을 결정하는 단계를 포함하는 KD-tree 생성 장치
|
| 11 |
11
제10항에 있어서, 상기 임계치는상기 해당 서브 공간을 정렬 방식으로 분할할 때 요구되는 내부 메모리의 크기를 기초로 결정되는 것을 특징으로 하는 KD-tree 생성 장치
|
| 12 |
12
제10항에 있어서, 상기 내부 노드는 상기 주어진 공간의 분할 면과 분할 면에 의해 분할된 복수의 서브공간으로 구성되는 것을 특징으로 하는 KD-tree 생성 장치
|
| 13 |
13
제10항에 있어서, 상기 트리 생성 유닛은상기 원시 데이터의 개수가 상기 임계치를 초과한다면 상기 해당 서브 공간을 비닝(binning) 방식으로 분할하여 상기 복수의 서브 공간들을 생성하는 제1 트리 생성부를 포함하는 것을 특징으로 하는 KD-tree 생성 장치
|
| 14 |
14
제10항에 있어서, 상기 트리 생성 유닛은 상기 원시 데이터의 개수가 상기 임계치를 초과하지 않는다면 상기 해당 서브 공간을 정렬(sorting) 방식으로 분할하여 복수의 서브 공간들을 생성하는 적어도 하나의 제2 트리 생성부를 포함하는 것을 특징으로 하는 KD-tree 생성 장치
|
| 15 |
15
제14항에 있어서, 제2 트리 생성부는상기 해당 서브 공간에 대한 정렬 방식의 분할을 병렬적으로 수행하여 상기 복수의 서브 공간을 생성하는 것을 특징으로 하는 KD-tree 생성 장치
|
| 16 |
16
제10항에 있어서, 상기 트리 생성 유닛은상기 복수의 서브 공간들의 분할 순서를 상기 KD-tree의 방문 순서로 변환하여 상기 복수의 서브 공간들을 메모리에 저장하는 노드 스케줄러를 포함하는 것을 특징으로 하는 KD-tree 생성 장치
|
| 17 |
17
제16항에 있어서, 상기 노드 스케줄러는상기 주어진 공간의 분할을 통해 생성된 노드의 주소 및 노드의 데이터를 입력받고 상기 노드의 데이터가 저장될 버스트 노드 엔트리(burst node entry)의 위치를 탐색하는 푸시 엔트리 선택부를 포함하고,상기 푸시 엔트리 선택부는 노드 주소와 버스트 주소를 비교하는 것을 특징으로 하는 KD-tree 생성 장치
|
| 18 |
18
제16항에 있어서, 상기 노드 스케줄러는노드 데이터가 저장될 공간이 없는 버스트 노드 엔트리를 탐색하는 팝 엔트리 선택부를 포함하는 것을 특징으로 하는 KD-tree 생성 장치
|
| 19 |
19
(a) 주어진 공간의 분할 방식을 결정하여 상기 주어진 공간을 복수의 서브 공간들(각각은 KD-tree의 노드를 형성함)로 분할하는 기능; 및(b) 상기 복수의 서브 공간들 각각을 상기 주어진 공간으로 설정하여 상기 단계 (a)를 반복하는 기능을 포함하고,상기 (a) 단계는 해당 서브 공간이 상기 KD-tree의 내부 노드에 해당하면 상기 내부 노드에 있는 원시 데이터의 개수가 임계치를 초과하는지 여부를 체크하고 상기 서브 공간(KD-tree 노드)의 상기 원시 데이터 개수를 기초로 상기 서브 공간의 분할 방식을 결정하는 기능을 포함하는 KD-Tree 생성 방법에 관한 컴퓨터 프로그램을 기록한 기록매체
|
