선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 본 논문에서는 연속적인 위치 변화에 따른 이동객체의 미래 위치 검색을 위한 색인 구조에 대한 갱신을 효과적으로 수행하기 위한 새로운 색인 구조를 제안하였다. 제안하는 색인 구조에서는 공간 분할 방식으로 색인을 구성하며 계속적인 위치 변화에 대한 갱신을 효과적으로 수행하기 위해 보조색인 구조를 이용하여 이동객체의 이전 위치가 저장되어 있는 노드를 직접 접근할 수 있도록 한다.
- 본 논문에서는 이동 객체의 미래 위치 검색을 지원하기 위해 기존 R-트리 기 반 색인 구조에서 발생하는 갱신 문제점을 해결하기 위한 새로운 색인 구조와 갱신기법을 제안한다. 제안하는 색인 구조는 이동 객체의 위치 변화를 빠르게 갱신하기 위해 공간분할 방식 색인 구조를 변형한 주 색인 구조(primary index structure)와 이동객체가 존재하는 단말노드를 직접 접근할 수 있는 보조 색인 구조 (secondary index structure)로 구성된다.
가설 설정
- 이때, a는 분할 차원을 표현하기 위해서 사용되는 정보를 나타낸다. 예를 들어, (그림 3)의 (a)와 같이 각 노드에 최대 3개의 객체를 저장되고 이에서 ow까지 이동 객체에 의해 4개의 분할된 노드 外 (, =1, 2, 3, 4)가 생성되었다고 가정하자. (그림 3)의 분할된 노드들은 먼저 1 차원의 5인 위치에 의해 분할되고 각 분할된 노드들은 다시 2차원의 5와 4인 위치에 의해 분할되었다.
- 이러한 상황에서 재삽입을 수행하기 위해 선택된 객체에 대한 새로운 위치를 갱신해야 할 경우 재삽입되는 이동 객체의 위치는 무의미하게 된다. 또한, 기존에 제안된 색인 구조는 객체의 이동방 향 및 속도가 일정 시간 동안 고정되어 있다고 가정하고 있다. 그러나 실제 응용분야에서 활용되는 이동객체들의 이동은 언제나 변화될 수 있다.
제안 방법
- R-트리 기 반 색인구조에서는 노드에 오버 플로우가 발생할 경우 분할로 인해 색인 구조의 높이가 증가되는 문제점을 해결하기 위해 오버플로우가 발생한 노드에 존재하는 일부 객체들에 대해 재삽입을 수행한다. 그러나 재삽입 연산은 많은 시간을 소요할 뿐만 아니라 재삽입 대상이 되는 이동 객체에 대해 새로운 위치를 갱신해야 할 필요가 있는 경우 재삽입 연산은 무의미해진다.
- 먼저 삽입 성능은 10, 000개에서 100,000개의 이동 객체를 삽입하면서 색인을 구성하는 시간을 비교한다.갱신 성능은 100,000개의 이동 객체를 삽입하여 색인을 구성하고 1,000개에서 10, 000개의 이동 객체에 대한 갱신을 수행하는 시간을 비교한다.본 논문에서 제시하는 부분 상향식 갱신과 완전 상향식 갱신에 대한 비교도 수행한다.
- 기존에 제안된 색인 구조와 갱신비용에 대한 성능평가 를 수행하기 위해 제안하는 색인 구조와 기존에 제안된 TPR-트리 그리고 T*- PR 트리와의 성능평가를 수행한다. 제안하는 색인 구조에 대한 갱신은 완전 상향식 갱신기법을 사용한다.
- 특히, 이동 객체의 미래 위치를 검색할 때 중간 노드에 존재하는 sf, 镐, t 岫을 이용하여 노드에 대한 영역을 확장시킨다. 따라서, 이동 객체의 검색에 영향을 미치는 sp vec, %, 站河을 고려하여 분할을 수행한다.
- 공간 분할 색인 구조는 재삽입을 수행하는 과정에서 자식 노드에 대한 분할이 발생하지 않는다면 재삽입되는 이동객체는 다시 이전 노드에 삽입되게 된다. 따라서, 제안하는 색인 구조에서는 노드에 오 버플로우가 발생할 경우 오버플로우가 발생한 노드와 형제노드를 병합하고 오버플로우가 발생한 노드에 존재하는 일부 객체들을 형제노드에 삽입하는 병합 분할(merge and split)을 수행한다. 오버플로우가 발생한 노드에 대해 병합분할이 가능한 노드를 검색하는 SearchSibling。은 부모 노 드에 존재하는 자식 노드들에 대한 분할 정보를 이용하여 형제노드를 검색한다.
- 만약 이동 객체의 이전 위치가 저장되어 있는 단말노드를 직접 접근할 수 있다면 이동 객체의 이전 위치를 검색하기 위한 시간을 절약할 수 있다. 따라서, 제안하는 색인 구조에서는 이동 객체의 계속적인 위치 변화에 따른 갱신비용을 감소시키기 위해 실제 이동 객체의 위치를 저장하는 단말노드를 직접 접근하기 위한 보조색인 구조를 사용한다.
- 본 논문에서 제시하는 부분 상향식 갱신과 완전 상향식 갱신에 대한 비교도 수행한다. 마지막으로 검색 성능은 검색해야 할 미래 시간을 5에서 20분까지 변화하면서 범위 검색을 수행한 시간을 비교한다. 편의상 제안하는 색인 구조는 PIS-트리 (Proposed Index Structure-tree) 라 한다.
- 제안하는 색인 구조의 우수성을 입증하기 위해 이동 객체의 삽입 성능, 갱신 성능 그리고 검색 성능을 비교한다. 먼저 삽입 성능은 10, 000개에서 100,000개의 이동 객체를 삽입하면서 색인을 구성하는 시간을 비교한다.갱신 성능은 100,000개의 이동 객체를 삽입하여 색인을 구성하고 1,000개에서 10, 000개의 이동 객체에 대한 갱신을 수행하는 시간을 비교한다.
- 제안하는 색인 구조 에서는 이동 객체의 갱신을 수행하기 위해 부분 상향식 갱 신 PBU와 완전 상향식 갱신 FBU을 제안하였다. 먼저 제안 하는 색인 구조에서 제안한 부분 상향식 갱신 기법과 완전 상향식 갱신 기법에 대한 성능 평가를 수행한다. 이동 객체 에 대한 갱신 비용을 비교하기 위해 100,000개 이동 객체를 삽입하고 1,000개에서 10, 000개의 이동 객체에 대한 갱신을 수행한다.
- 또한, 색인 구조의 크기가 증가할수록 이동 객체의 삽입이나 갱신과정에서 탐색해야 할 노드의 수가 증가된다. 먼저 제안하는 색인 구조와 기존에 제안된 색인 구조에 대해 이동 객체를 삽입하여 구성된 색인 구조의 크기를 실험을 통해 비교분석한다. 해쉬 구조로 구성된 보조색인 구조의 크기는 주 색인 구조의 크기에 비해 상대적으로 작아 실험평가에서 보조색인 구조의 크기는 고려하지 않는다[10].
- 갱신 성능은 100,000개의 이동 객체를 삽입하여 색인을 구성하고 1,000개에서 10, 000개의 이동 객체에 대한 갱신을 수행하는 시간을 비교한다.본 논문에서 제시하는 부분 상향식 갱신과 완전 상향식 갱신에 대한 비교도 수행한다. 마지막으로 검색 성능은 검색해야 할 미래 시간을 5에서 20분까지 변화하면서 범위 검색을 수행한 시간을 비교한다.
- 제안하는 색인 구조에서는 보조색인 구조를 통해 이동객체가 저장된 단말노드에 직접 접근하고 위치 변화를 갱신한다. 본절에서는 이동 객체의 위치 변화에 대한 갱신을 효과적으로 처리하기 위해 부분 상향식 갱신 (PBU : Partial Bottom-up Update) 기법과 완전 상향식 갱신(FBU : Full Bottom-up Update) 기법을 제안한다. 먼저, 부분 상향식 갱신기법에 대해 기술하고 부분 상향식 갱신 기법을 문제점을 해결하기 위한 완전 상향식 갱신기법을 기술한다.
- 성능평가를 위해 제안하는 색인 구조, TPR-트리 그리고 *- TPR 트리를 펜티엄 IV 2.8GHz 프로세서에 256Mbyte의 메모리를 가지는 시스템에서 구현한다. 구현한 색인 구조에서 노드의 크기는 4kbyte이며 C언어를 통해 구현한다.
- 범위 검색은 현재 및 미래 시점에서 주어진 공간적인 범위 내에 존재하는 이동 객체를 검색한다. 실험에서 사용한 검색은 공간 분할 기반 색인 구조로 제안된 기존에 기법을 이용한다 M. 제안하는 색인 구조의 검색 성능을 비교하기 위해 검색해야 할 미래 시간을 5에서 20분까지 변경하면서 범위 검색을 수행한 시간을 측정한다. (그림 26)에서 (그림 28)은 범위 검색을 수행한 시간을 나타낸 것이다.
- 또한, 새로운 이동 객 체를 삽입하기 위한 위치를 판별하는 것이 단순하기 때문에 이동 객체를 삽입하는 시간을 절약할 수 있다. 이 동 객체의 갱신비용을 감소시키기 위해 실제 이동 객체의 위치를 저장하는 단말노드를 직접 접근하기 위한 보조색인 구조를 사용하고 각 노드에는 부모노드에 대한 포인터를 유지하여 이동 객체의 갱신으로 노드의 변경이 발생할 경우 색인 구조 전체를 순회하지 않고 상향식으로 갱신을 수행한다. 또한, 노드의 팬아웃을 증가시키기 위해 중간 노드에는 분할된 실제 영역을 표현하는 것이 아니라 필요한 분할 정보를 kd-트리로 표현한다.
- 먼저 제안 하는 색인 구조에서 제안한 부분 상향식 갱신 기법과 완전 상향식 갱신 기법에 대한 성능 평가를 수행한다. 이동 객체 에 대한 갱신 비용을 비교하기 위해 100,000개 이동 객체를 삽입하고 1,000개에서 10, 000개의 이동 객체에 대한 갱신을 수행한다. (그림 20)에서 (그림 22)는 이동 객체의 분포 특성에 따른 갱신 시간을 비교한 것이다.
- 제안하는 색인 구조에 대한 갱신은 완전 상향식 갱신기법을 사용한다. 이동 객체의 갱신 기법을 비교하기 위해 100,000개의 이동 객체의 삽입하고 1,000개에서 10, 000개의 이동 객체를 갱신하기 위해 소요되는 시간을 비교 분석한다. (그림 23)에서 (그림 25)는 이동 객체의 분포특성에 따른 갱신 시간을 비교한 것이다.
- 이동 객체의 삭제로 노드의 정보가 변경되면 AdjustNodeQ를 수행하여 변경된 노드의 정보를 부모 노드에 반영한다. 이동 객체의 이전 위치를 삭제하면 헤더에 존재하는 부모노드에 포인터를 통해 부모노드를 읽고 CaluateCont应nsO를 수행하여 부모노드의 영역 내에 이동 객체의 새로운 위치가 포함되는지를 판별한다. 이동 객체의 새로운 위치가 부모 노드 내에 포함되면 FindNodeO를 수행하여 부모노드를 기준으로 이동 객체의 새로운 위치를 삽입할 단말노드를 검색하고 이동 객체를 삽입한다.
- 기존 R-트리 기반의 색인 구조는 이동객체가 삽입되거나 이동 객체의 위치 변화에 따라 갱신을 수행할 때 이동객체들을 포함하는 최소 영역을 생성하기 위해 많은 시간을 소요하며 노드들 사이에 겹침 영역이 발생하기 때문에 이동 객체를 삽입하거나 갱신하기 위한 최적의 노드를 선택하기 위해 많은 시간을 소요한다. 이러한 문제점을 해결하기 위해 제안하는 색인 구조는 분할된 영역들 사이에 겹침이 발생하지 않도록 공간 분할 방식으로 색인을 구성한다. 따라서, 분할된 노드에 존재하는 객체들을 포함하는 최소 영역을 생성하기 위한 비용을 제거할 수 있다.
- 중간 노드에 저장되는 kd-트리는 (그림 3)에서 보는 것과 같이 kd-트리는 이진 트리 형태로 구성되며 이러한 이진 트리의 자식 노드를 접근하기 위해서는 포인터가 필요하다. 이러한 포인터를 제거하기 위해 제안하는 색인 구조 에서는 kd-트리를 깊이 우선 또는 넓이 우선 방식에 의해 트리를 순회한 순서대로 저장한다.
- 제안하는 PIS-트리에서는 이동 객체의 삽입이나 갱신으로 인해 노드에 오버플로우가 발생할 경우 재삽입을 수행하지 않고 오버플로우가 발생한 노드에 대해 부모노드를 직접 접근하여 형제노드와 병합을 수행한다. 이로 인해 노드의 재삽입으로 인해 소요되는 시간을 단축시킬 수 있고 분할로 인해 노드의 크기가 증가되는 문제점을 해결한다.
- 이동 객체의 계속적인 위치 변화에 따른 갱신을 효과적으로 수행하기 위해서는 이동 객체의 위치 변화에 따라 탐색 해야 할 노드의 수를 감소시켜야 한다. 제안하는 색인 구조 에서는 이동 객체의 갱신을 수행하기 위해 부분 상향식 갱 신 PBU와 완전 상향식 갱신 FBU을 제안하였다. 먼저 제안 하는 색인 구조에서 제안한 부분 상향식 갱신 기법과 완전 상향식 갱신 기법에 대한 성능 평가를 수행한다.
- 또한, 有는 S”에 의해 분할된 단말 노드 如과 如을 생성하고 改는 S& 과 S22에 의해 분할된 단말노드 nw „22, 响을 생성한다. 제안하는 색인 구조는 (그림 2)와 같이 주 색인 구조와 보조색인 구조로 구성되어 있다. 주 색인 구조는 위치 변화에 따른 노드의 재구성 시간을 감소시키기 위해 공간분할 방식 색인 구조를 변형한 높이 균형 트리로 이동 객체의 위치검색을 위해 실제 이동 객체의 위치를 저장한다.
- 제안하는 색인 구조는 공간 분할 방식의 색인 구조로써 (그림 1)과 같은 분할 영역에 대해 (그림 2)와 같이 구성된다. (그림 1)에서 s, 는 분할 위치, 분할영역에 표시된 검은색의 화살표는 단말노드에 대한 속도 그리고 흰색 화살표는 중간 노드에 대한 속도를 나타낸다"(그림 1)의 분할 영역은 2차원 데이터 공간에 대해 %을 기준으로 분할된 중간 노드邕과 %을 생성한다.
- 제안하는 색인 구조는 이동 객체의 계속적인 위치 변화에 대한 갱신을 효과적으로 수행하면서 현재 및 미래 위치를 검색하기 위한 색인 구조이다. 기존 R-트리 기반의 색인 구조는 이동객체가 삽입되거나 이동 객체의 위치 변화에 따라 갱신을 수행할 때 이동객체들을 포함하는 최소 영역을 생성하기 위해 많은 시간을 소요하며 노드들 사이에 겹침 영역이 발생하기 때문에 이동 객체를 삽입하거나 갱신하기 위한 최적의 노드를 선택하기 위해 많은 시간을 소요한다.
- 제안하는 색인 구조는 이동 객체의 동적 변화 특성을 고려하여 현재 및 미래 위치를 검색할 때 탐색해야 할 노드의 수를 감소시킬 수 있도록 분할 위치를 선택해야 한다. 특히, 이동 객체의 미래 위치를 검색할 때 중간 노드에 존재하는 sf, 镐, t 岫을 이용하여 노드에 대한 영역을 확장시킨다.
- 이로 인해, 이동 객체의 위치를 갱신하기 위해 많은 시간을 소요한다. 제안하는 색인 구조는 이동 객체의 새로운 위치를 갱신하기 위해 이동 객체의 이전 위치가 저장되어 있는 단말노드를 직접 접근한다. 이동 객체의 갱신 으로 노드의 정보가 변경될 경우 노드의 헤더에 존재하는 부모노드에 대한 포인터를 통해 상향식 갱신을 수행한다.
- 본 논문에서는 이동 객체의 미래 위치 검색을 지원하기 위해 기존 R-트리 기 반 색인 구조에서 발생하는 갱신 문제점을 해결하기 위한 새로운 색인 구조와 갱신기법을 제안한다. 제안하는 색인 구조는 이동 객체의 위치 변화를 빠르게 갱신하기 위해 공간분할 방식 색인 구조를 변형한 주 색인 구조(primary index structure)와 이동객체가 존재하는 단말노드를 직접 접근할 수 있는 보조 색인 구조 (secondary index structure)로 구성된다. 제안하는 색인 구조는 분할된 영역들 사이에 겹침이 발생하지 않도록 전체 공간을 분할하기 때문에 객체들이 존재하는 최소 영역을 생성하기 위한 시간을 제거할 수 있다.
- 본 논문에서는 연속적인 위치 변화에 따른 이동객체의 미래 위치 검색을 위한 색인 구조에 대한 갱신을 효과적으로 수행하기 위한 새로운 색인 구조를 제안하였다. 제안하는 색인 구조에서는 공간 분할 방식으로 색인을 구성하며 계속적인 위치 변화에 대한 갱신을 효과적으로 수행하기 위해 보조색인 구조를 이용하여 이동객체의 이전 위치가 저장되어 있는 노드를 직접 접근할 수 있도록 한다. 각 노드에는 부모 노드를 직접 접근하기 위한 포인터를 유지하고 이동객체의 갱신으로 노드의 변경이 발생할 경우 색인 구조 전체를 순회하지 않고 상향식으로 갱신을 수행한다.
- 뿐만 아니라, 다수 사용자를 지원하는 환경에서는 이동 객체에 대한 검색을 지연시켜 검색 성능을 저하시킨다. 제안하는 색인 구조에서는 보조색인 구조를 통해 이동객체가 저장된 단말노드에 직접 접근하고 위치 변화를 갱신한다. 본절에서는 이동 객체의 위치 변화에 대한 갱신을 효과적으로 처리하기 위해 부분 상향식 갱신 (PBU : Partial Bottom-up Update) 기법과 완전 상향식 갱신(FBU : Full Bottom-up Update) 기법을 제안한다.
- 은 자식 노드에 대한 포인터이다. 제안하는 색인 구조에서는 이동 객체의 미래 위치를 검색하는 과정에서 불필요한 노드의 확장으로 인해 검색 성능이 저하되는 문제점을 해결하기 위해 분할영역 劝에 존재하는 이동객체들이 노드를 벗어나는 시간 払0을 함께 저장한다. 분할된 노드에 대한 갱신 시간이 이고분할된 영역을 벗어나는 시간t空, 일 때, 시점 网서 이동 객체에 대한 검색을 수행하기 위해서는 이동 객체에 대한 속도정보 功源。을 이용하여 시점 £에서 자식 노드에 존재하는 이동 객체들이 이동할 수 있는 영역으로 노드를 확장한다.
- 그러나 이러한 분할 방식은 노드의 공간 활용률을 저하시킬 수 있기 때다. 제안하는 색인 구조에서는 중간 노드의 분할을 수행하기 위해 먼저 중간 노드에 존재하는 분할 정보를 이용하여 연속 분할을 수행하지 않는 위치를 선택한다. 자식 노드에 대한 연속 분할이 발생하지 않는 위치를 선택하면 자식 노드에 대한 sp vec, 妃沪 妃E를 이용하여 이동 객체의 검색을 향상시킬 수 있는 분할 위치를 판별한다.
- 또한, 각 이 동 객체에 대해 1,000개의 이동변화를 갖도록 한다. 제안하는 색인 구조의 우수성을 입증하기 위해 이동 객체의 삽입 성능, 갱신 성능 그리고 검색 성능을 비교한다. 먼저 삽입 성능은 10, 000개에서 100,000개의 이동 객체를 삽입하면서 색인을 구성하는 시간을 비교한다.
- 이에 반해, 이동 객체의 새로운 위치가 이동 객체의 이전 위치가 존재하는 단말노드의 영역 내에 존재하지 않는 경우에는 단말 노드에 존재하는 이동 객체의 위치를 삭제하고 상향식으로 갱신을 수행한다. 즉, 주색인 구조 전체를 순회하면서 이동 객체의 새로운 위치를 삽입하기 위한 단말노드를 검색하고 새로운 위치를 삽입한다.
대상 데이터
- 구현한 색인 구조에서 노드의 크기는 4kbyte이며 C언어를 통해 구현한다. 성능평가에 사용된 데이터 집합은 GSTD113]을 통해 1000x1000km의 2차원 공간에서 균등(uniform), 가우시안(gaussian) 그리고 스큐(skew) 분포로 존재하는 100,000개 이동 객체를 생성한다. 또한, 각 이 동 객체에 대해 1,000개의 이동변화를 갖도록 한다.
- 이동 객체에 대한 삽입 성능을 평가하기 위해 10, 000개에서 100,000개의 이동 객체를 삽입하는 시간을 분석한다. (그림 17)에서 (그림 19)는 이동 객체에 대한 삽입 시간을 나타낸 것이다.
- (그림 14)에서 (그림 16)은 이동 객체의 삽입으로 생성된 색인 구조의 크기를 나타낸 것이다. 이동 객체의 삽입으로 생성되는 색인 구조의 크기를 비교하기 위호H1Q000 개에서 100,000개까지의 이동 객체를 삽입한다. (그림 14)는 GSDT을 통해 균등분포 형태로 생성한 이동 객체를 삽입 하여 생성한 색인 구조의 크기를 나타낸 것이다.
이론/모형
- 따라서, 미래 위치를 검색하는 과정에서 검색 성능을 저하시킬 수 있다. 이동 객체의 미래 위치를 검색을 지원하기 위해 제안된 TPR-트리에서 삽입과 삭제는 다차원색인 구조로 제안된 R*- 트리의 알고리즘을 사용하고 있다. 그러나 R*- 트리는 고정된 객체들을 색인하기 때문에 이동 객체를 색인하기 위해서는 적합하지 못하다.
- 기존에 제안된 색인 구조와 갱신비용에 대한 성능평가 를 수행하기 위해 제안하는 색인 구조와 기존에 제안된 TPR-트리 그리고 T*- PR 트리와의 성능평가를 수행한다. 제안하는 색인 구조에 대한 갱신은 완전 상향식 갱신기법을 사용한다. 이동 객체의 갱신 기법을 비교하기 위해 100,000개의 이동 객체의 삽입하고 1,000개에서 10, 000개의 이동 객체를 갱신하기 위해 소요되는 시간을 비교 분석한다.
성능/효과
- (그림 17)에서 (그림 19)는 이동 객체에 대한 삽입 시간을 나타낸 것이다. 기존에 제안된 TPR-트리와 T*- PR 트리는 삽입 되는 이동 객체의 수가 증가할수록 삽입 시간이 급격히 증가되지만 제안하는 색인 구조는 삽입되는 이동 객체의 수가 증가되어도 삽입 시간에 많은 영향을 받지 않는다. 제안하는 PIS-트리는 기존에 제안된 TPR-트리에 비해 450%의 성능 향상을 보이며 T*- PR 트리에 비해서는 약 520%의 성능 향상을 보인다.
- 공간 분할 방식의 색인 구조에서는 이동 객체의 갱신을 수행한 위치는 대부분 이동 객체가 존재하는 단말 노드의 형제 노드에 존재한다. 따라서, 색인 구 조의 높이가 증가할수록 부분 상향식 갱신 기법보다는 완전 상향식 갱신 기법보다 탐색해야 할 노드의 수를 감소시킨 다. 이로 인해 완전 상향식 갱신 기법이 부분 상향식 갱신 기법보다 우수한 성능을 보인다.
- 그러나 갱신되는 이동 객체의 수가 증가할수록 완전 상향식 갱신 기법이 부분 상향식 갱신 기 법보다 우수하다. 상향식 갱신 기법은 1,000개의 이동 객체 를 갱신할 때에는 약 10% 성능이 저하되지만 갱신되는 이동 객체의 수가 증가할수록 약 45% 성능이 향상을 보인다. 부분 상향식 갱신은 이동 새로운 위치 단말 노드의 영역 내에 포함되어 있는 경우에는 부모 노드를 직접 접근하여 상향식 갱신을 수행한다.
- (그림 20)에서 (그림 22)는 이동 객체의 분포 특성에 따른 갱신 시간을 비교한 것이다. 성능 평가 결과 1,000개의 이동 객체에 대한 갱신을 수행할 경우에는 완전 상향식 갱신이 부분 상향식 갱신 기법보다 성능 약간 저하 되는 것을 알 수 있다. 그러나 갱신되는 이동 객체의 수가 증가할수록 완전 상향식 갱신 기법이 부분 상향식 갱신 기 법보다 우수하다.
- 이로 인해 색인 구조의 크기를 감소시킬 수 있다. 성능평가 결과 제안하는 색인 구조는 기존에 제안된 TPR-트리와 T*- PR 트리에 비해 색인 구조의 크기가 감소되는 것을 알 수 있다. 제안하는 PIS-트 리는 기존에 제안된 색인 구조에 비해 29~58%의 성능 향상을 보인다.
- 또한, 노드에 오버 플로우가 발생할 경우 직접 분할을 수행하지 않고 형제노드와 병합분할을 수행한다. 성능평가 결과 제안하는 색인 구조는 삽입 성능, 갱신 성능, 검색성능 모두에 대해 우수함을 보였다.
- 1%~2% 범위에 존재하는 1,000개의 검색을 수행한 평균 시간을 사용한다. 성능평가 결과 현재 시점에서 검색한 결과와 유사하게 기존에 제안된 색인 구조들은 미래 시간이 증가될수록 검색해야 할 노드의 수가 증가되어 검색시간이 저하됨을 알 수 있다. 이에 반해 제안하는 색인 구조는 검색해야할 미래 시간이 증가되어도
- 성능평가 결과 제안하는 색인 구조는 기존에 제안된 TPR-트리와 T*- PR 트리에 비해 색인 구조의 크기가 감소되는 것을 알 수 있다. 제안하는 PIS-트 리는 기존에 제안된 색인 구조에 비해 29~58%의 성능 향상을 보인다.
- 기존에 제안된 TPR-트리와 T*- PR 트리는 삽입 되는 이동 객체의 수가 증가할수록 삽입 시간이 급격히 증가되지만 제안하는 색인 구조는 삽입되는 이동 객체의 수가 증가되어도 삽입 시간에 많은 영향을 받지 않는다. 제안하는 PIS-트리는 기존에 제안된 TPR-트리에 비해 450%의 성능 향상을 보이며 T*- PR 트리에 비해서는 약 520%의 성능 향상을 보인다.
- 이에 반해, 제안하는 색인 구조는 갱신되는 이동 객체의 수가 증가되어도 갱신 시간에 많은 영향을 받지 않는다. 제안하는 PIS-트리의 완전 상향식 갱신 기법은 기존에 제안된 TPR-트리에 비해 약 340%의 성능 향상을 보이며 T*- PR 트리에 비해서는 약 460%의 성능 향상을 보인다. 기존에 제안된 색인 구조들은 이동 객체의 이전 위치가 저장되어 있는 단말 검색하여 이전 위치를 삭제하고 이동 객체의 새로운 위치를 삽입하는 과정을 수행하면서 이동 객 체의 위치를 갱신한다.
- 성능의 저하가 거의 없는 것을 알 수 있다. 제안하는 색인 구조는 TPR-트리에 비해 약 180% 성능 향상을 보이며 *- TPR 트리에 비해서는 약 140% 성능 향상을 보인다.
- 제안하는 색인 구조는 공간 분할 방식을 이용하여 색인을 구성하기 때문에 분할된 영역들 사이에 겹침이 발생하지 않으며 주 색인 구조의 중간 노드에는 자식 노드에 대한 속도정보를 저장하기 때문에 이동 객체의 미래 위치를 검색할 수 있다. 또한, 이동 객체의 미래 위치를 검색하는 과정에서 불필요한 영역의 확장을 방지하기 위해 払, 와歸”을 이용하여 중간노드에 유지한다.
- 기존에 제안된 색인 구조들은 미래 시간이 증가할수록 검색 성능이 급격히 저하되는 문제점이 있다. 제안하는 색인 구조는 자식 노드에 존재하는 이동 객체의 속도뿐만 아니라 노드가 갱신된 시간과 노드 내에 존재하는 이동객체들 이 영역을 벗어나는 시간 등을 표현하기 때문에 탐색해야 할 노드의 수를 감소시킬 수 있다. 또한, 오버플로우가 발생한 노드에 대한 직접적인 분할을 수행하지 않기 때문에 색인 구조의 크기를 감소시킬 수 있다.
후속연구
- 향후 연구방향으로 제안하는 색인 구조를 통해 이동객체의 연속 질의 처리기법에 대한 연구를 수행할 예정이며 다수의 연속 질의를 효과적으로 처리하기 위한 메모리 기반 색 인구조에 대한 연구를 수행할 예정이다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.