선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 본 논문에서는 위치기반 서비스의 중심이 되는 이동 객체의 계속적인 위치 변화를 효과적으로 갱신하면서 이동 객체의 미래 위치 검색을 지원하기 위한 색인 구조를 제안한다. 제안하는 색인 구조는 기존의 공간 분할 방식의 색인 구조를 변형하여 이동 객체의 미래 위치를 검색할 수 있으며 계속적인 이동객체의 변화에 따른 갱신비용을 감소시키기 위해 이동객체가 저장된 단말노드를 직접 접근하기 위한 보조색인 구조를 사용한다.
- 본 논문에서는 이동 객체의 연속적인 위치 변화에 대한 갱신을 효과적으로 수행하면서 이동 객체의 미래 위치를 지원하는 색인 구조를 제안하였다. 제안하는 색인 구조는 이동객체의 계속적인 위치를 변화에 따른 갱신을 효과적으로 수행하기 위해 공간분할 방식에 의해 색인을 구성하고 각 노드에는 부모노드를 직접 접근하여 상향식 갱신을 수행한다.
제안 방법
- S. Saltenis는 기존 R*-트리 기반의 색인 구조를 이용하여 이동 객체에 대한 현재 및 미래 위치에 대한 효율적인 검색을 지원하기 위해 TPR-트리 (Time Parameterized R-tree)를 제안하였다. TPR-트리는 시간 파라미터 경계 영역 (time parameterized bounding rectangle)을 이용하여 현재 및 미래 위치에 대한 검색을 지원한다.
- Prabhakar는 이동 객체의 이동 변화에 따라 색인 구조에 대한 갱신비 용을 줄이기 위해 가능한 객체의 최대 속도를 이용하여 색인을 구성하는 VCI~트리(Velocity Constrained Indexing-Tree) 라는 색인 구조를 제안하였다 [8]. VCI-트리는 기존의 R-트리 기반 색인구조에 미래를 검색하기 위한 Vmax 필드를 추가하였다. Vg 필드는 자식 노드에 존재하는 이동객체의 가장 빠른 속도값을 나타내며 이를 통해 미래 위치를 검색한다.
- 그림4는 제안하는 색인 구조의 삽입 알고리즘을 나타낸 것이다. 객체 e을 삽입하기 위해서 먼저 SearchHashTableO을 수행하여 서버로 전송된 객체의 위치가 기존에 삽입된 이후 갱신을 요청하는 것인지 새로운 객체의 삽입인지를 판별한다.만약 객체가 이전 위치에 대한 갱신을 요청하는 것이라면 UpdateNodeO을 수행하여 객체의 위치를 갱신한다.
- 제안하는 색인 구조는 이동객체의 계속적인 위치를 변화에 따른 갱신을 효과적으로 수행하기 위해 공간분할 방식에 의해 색인을 구성하고 각 노드에는 부모노드를 직접 접근하여 상향식 갱신을 수행한다. 또한 보조색인 구조를 이용하여 이동객체가 저장되어 있는 단말노드를 직접 접근할 수 있도록 하였다. 실험을 통해 제안된 색인 구조는 기존 TPR-트리에 비해 갱신 및 검색 성능이 향상됨을 보였다.
- 삽입 성능을 비교하기 위해 1만개에서 10만개의 이동객체를 삽입하는 시간을 비교한다. 또한, 갱신 성능은 10만개의 이동객체를 삽입하고 기존에 삽입 된 이동객체에 대해 1천개에서 1만개까지의 위치를 갱 신한 시간을 비교한다. 그림 10은 삽입 성능을 수행한 결과이고 그림 11은 갱신 성능을 수행한 결과이다.
- 제안하는 색인 구조는 공간 분할 방식을 이용하여 색인을 구성하기 때문에 분할된 영역들 사이에 겹침이 발생하지 않으며 주 색인 구조의 중간 노드에는 자식 노드에 대한 속도정보를 저장하기 때문에 이동 객체의 미래 위치를 검색할 수 있다. 또한, 이동객체의 미래 위치를 검색하기 위해 불필요한 영역의 확장을 방지하기 위해 tesp을 이용하여 색인을 구성한다. 그림4는 제안하는 색인 구조의 삽입 알고리즘을 나타낸 것이다.
- 제안하는 색인 구조의 이동객체의 계속적인 위치 변화에 따른 갱신비용을 최소화하면서 이동객체의 미래 위치를 지원하기 위한 색인 구조이다. 먼저 제안하는 색인 구조와 TPR-트리에 대한 삽입 성능 및 갱신 성능을 비교한다. 삽입 성능을 비교하기 위해 1만개에서 10만개의 이동객체를 삽입하는 시간을 비교한다.
- 먼저 제안하는 색인 구조와 TPR-트리에 대한 삽입 성능 및 갱신 성능을 비교한다. 삽입 성능을 비교하기 위해 1만개에서 10만개의 이동객체를 삽입하는 시간을 비교한다. 또한, 갱신 성능은 10만개의 이동객체를 삽입하고 기존에 삽입 된 이동객체에 대해 1천개에서 1만개까지의 위치를 갱 신한 시간을 비교한다.
- 특정 시간 동안 서버로 위치를 전송하지 않는 객체는 객체에 장애가 발생하거나 서비스를 중지한 것으로 판별한다. 서비스를 중지한 이동 객 체에 대한 삭제를 수행하기 위해 제안하는 색인 구조에서는 객체를 삽입할 단말노드를 접근하면 단말 노드에 존재하는 객체에 대해 DeleteExpObjectO를 수행한다. DeleteExpObjectO는 단말노드에 존재하는 객체 o, -에 대해 현재 서버로 전송된 객체 e의 갱신 시간을 비교하여 MaxT을 초과하도록 서버로 자신의 위치를 전송하는지 않는 객체o1는 서비스를 중지한 것으로 판별하고 삭제한다.
- 성능평가를 위해 제안하는 색인 구조와 TPR-트리 와 제안하는 색인 구조를 256M의 메모리는 갖는 펜티엄 IV 1.7GHz에서 C 언어를 통해 구현하였다. 실험을 위해 사용된 데이터는 GSTDU3]을 통해 10만개의 이동객체를 생성한다.
- 이동 객체를 삽입할 단말노드를 검색하면 먼저 객체의 삽입으로 오버 플로우가 발생하는지를 검사한다. 객 체의 삽입으로 오버 플로우 발생하지 않는 경우에는 객체를 삽입하고 객체의 삽입으로 변경된 노드의 정보를 부모 노드에 반영한다.
- 이동 객체의 삽입 또는 위치 변화에 따른 갱신을 수행하는 과정에서 노드에 오버플로우가 발생하면 오버플로우가 발생한 노드의 형제노드를 검색하여 병합을 수행하여 오버플로우가 발생한 노드에 존재하는 객체의 일부를 형제노드에 삽입하여 오버플로우에 대한 처리를 수행한다. 그러나 형제 노드와 병합을 수행하여 오버플로우를 처리할 수 없을 경우에는 분할을 수행한다.
- 그림7은 UpdateNodeQ 알고리즘을 나타낸 것이다. 이동 객체의 이전 위치가 저장되어 있는 단말노드에 접근하면 새로운 위치가 단말 노드의 영역 내에 포함되는지를 판별하기 위해 ReadHeaderQ를 수행하여 단말 노드의 헤더를 읽고 헤더에 포함된 단말노드의 영역을 이용하여 새로운 객 체의 위치가 단말 노드에 포함되는지를 판별한다. 객체의 새로운 위치가 단말노드 내에 포함되는 경우에는 ReplacePositionO을 수행하여 객체의 이전 위치를 삭제하고 객체의 새로운 위치를 단말노드에 삽입한다.
- 또한 중간 노드들 사이에 겹침 영역이 발생할 경우 루트노드에서부터 단말노드를 순회해야 할 경로가 증가되어 갱신비용 을 증가시킨다. 이러한 문제를 해결하기 위해 D. S. Kwone 다차원 데이터색인 구조의 대표적인 R-트리 기반 색인구조에서 동적인 변화 특성을 갖고 빈번한 갱신을 수행 요청을 효율적으로 처리하기 위해 LUR- 트리를 제안하였다 [11]. LUR-트리는 해쉬테이블을 통해 이동객체가 저장되어 있는 단말노드를 접근하여 갱신을 수행한다.
- 제안하는 색인 구조는 이동객체의 계속적인 위치 변화를 효과적으로 갱신하면서 미래 위치 검색을 지원한다. 제안하는 색인 구조는 갱신비용을 감소시키기 위해 공간분할 방식에 의해 색인을 구성하고 이전에 삽입된 이동객체에 대한 갱신은 색인 구조 전체를 순회하지 않고 상향식으로 수행한다. 그림 1은 제안하는 색인 구조를 나타낸 것이다.
- 본 논문에서는 위치기반 서비스의 중심이 되는 이동 객체의 계속적인 위치 변화를 효과적으로 갱신하면서 이동 객체의 미래 위치 검색을 지원하기 위한 색인 구조를 제안한다. 제안하는 색인 구조는 기존의 공간 분할 방식의 색인 구조를 변형하여 이동 객체의 미래 위치를 검색할 수 있으며 계속적인 이동객체의 변화에 따른 갱신비용을 감소시키기 위해 이동객체가 저장된 단말노드를 직접 접근하기 위한 보조색인 구조를 사용한다.
- 제안하는 색인 구조는 이동객체의 계속적인 위치 변화를 효과적으로 갱신하면서 미래 위치 검색을 지원한다. 제안하는 색인 구조는 갱신비용을 감소시키기 위해 공간분할 방식에 의해 색인을 구성하고 이전에 삽입된 이동객체에 대한 갱신은 색인 구조 전체를 순회하지 않고 상향식으로 수행한다.
- 이동 객체의 갱신으로 노드에 변경이 발생하였을 경우 부모 노드를 직접 접근하여 변경된 노드의 정보를 반영한다. 제안하는 색인 구조는 이동객체의 계속적인 위치 변화에 따른 MBR 영역의 재구성 시간을 제거하기 위해 공간 분할에 의해 색인을 구성한다. sp는 단말노드에 존재하는 객체들을 포함하는 영역으로 공간 분할에 의해 생성된 영역으로 #와 같이 표현된다.
- 본 논문에서는 이동 객체의 연속적인 위치 변화에 대한 갱신을 효과적으로 수행하면서 이동 객체의 미래 위치를 지원하는 색인 구조를 제안하였다. 제안하는 색인 구조는 이동객체의 계속적인 위치를 변화에 따른 갱신을 효과적으로 수행하기 위해 공간분할 방식에 의해 색인을 구성하고 각 노드에는 부모노드를 직접 접근하여 상향식 갱신을 수행한다. 또한 보조색인 구조를 이용하여 이동객체가 저장되어 있는 단말노드를 직접 접근할 수 있도록 하였다.
- 단말노드의 헤더에 존재하는 sp는 단말노드에 존재하는 이동객체의 갱신으로 노드에 대한 변경이 발생할 경우 하향식으로 부모 노드를 직접 접근하여 갱신하기 위한 부모노드에 대한 포인터이다. 제안하는 색인 구조는 이동객체의 삽입이나 기존에 삽입된 이동객체 에 대한 갱신으로 단말 노드에 대한 정보가 변경되었을 경우 pptr을 이용하여 부모노드를 직접 접근할 수 있도록 한다.
- 제안하는 색인 구조는 자식 노드에 대한 분할 영역을 표현하기 위해 kd-트리의 중간 노드는 자식 노드에 대한 분할 정보를 나타내기 위한os>에 의해 나타낸다.
- 그림 1은 제안하는 색인 구조를 나타낸 것이다. 제안하는 색인 구조는 주 색인 구 조 (primary index structure) 와 보조 색인 구조 (secondary index structure)로 구성되어 있다. 주 색 인 구조는 미래 위치를 검색하기 위해 실제 이동 객체 를 저장한다.
- 제안하는 색인 구조에서는 이전에 삽입된 이동객체 의 위치가 변경되어 갱신을 수행할 경우 보조색인 구조를 통해 이동객체의 이전 위치가 저장된 단말노드 를 접근하여 상향식으로 갱신을 수행한다. 따라서, 이동객체가 저장된 이전 위치를 찾기 위해 주색인 구조를 순회할 필요가 없다.
- 제안하는 색인 구조의 이동객체의 계속적인 위치 변화에 따른 갱신비용을 최소화하면서 이동객체의 미래 위치를 지원하기 위한 색인 구조이다. 먼저 제안하는 색인 구조와 TPR-트리에 대한 삽입 성능 및 갱신 성능을 비교한다.
- 중간 노드에 오버플로우가 발생할 경우에도 단말 노 드와 유사하게 분할된 형제 노드와 합병이 가능한 노드 가 존재하는지 판별하여 오버플로우에 대한 처리를 수 행한다. 만약 오버플로우가 발생한 중간 노드와 합병이 가능한 중간 노드가 존재하지 않을 경우에는 중간 노드에 대한 분할을 수행한다.
대상 데이터
- 7GHz에서 C 언어를 통해 구현하였다. 실험을 위해 사용된 데이터는 GSTDU3]을 통해 10만개의 이동객체를 생성한다. 표 1은 성능 평가에 사용된 파라미터를 나타낸다.
이론/모형
- 이동 객체에 대한 효과적인 검색을 수행하기 위해서는 계속적인 이동객체의 위치정보를 갱신할 필요가 있다. 그러나 기존의 R-트리 기반의 색인 구조는 루트노드에서 단말노드까지 순회하면서 객체의 이전 객체의 위치정보를 삭제하고 새로운 위치를 삽입하는 하향식(top-down) 갱신기법을 사용하였다. 또한 중간 노드들 사이에 겹침 영역이 발생할 경우 루트노드에서부터 단말노드를 순회해야 할 경로가 증가되어 갱신비용 을 증가시킨다.
- 실제 위치기반 서비스의 대상이 되는 객체들은 동적인 변화 특성을 갖고 계속적인 위치 변화를 갖기 때문에 기존 R-트리 색인 구조를 사용할 경우 많은 갱신을 소요한다. 또한, 기존에 제안된 R-트리 기반의 색인 구조는 객체의 위치를 갱신하기 위해 루트노드에서 단말노드를 순회하면서 객체의 이전 객체의 위치정보를 삭제하고 새로운 위치를 삽입하는 하향식(top-down) 갱신기법을 사용한다. 이로 인해 갱신을 위해 접근해야 할 노드의 수가 증가되고 많은 갱신비 용을 소용한다.
성능/효과
- 또한 보조색인 구조를 이용하여 이동객체가 저장되어 있는 단말노드를 직접 접근할 수 있도록 하였다. 실험을 통해 제안된 색인 구조는 기존 TPR-트리에 비해 갱신 및 검색 성능이 향상됨을 보였다. 향후 연구방향으로 색인 구조를 통한 다양한 질의 처리 기법에 대한 연구를 수행할 예정이다
- TPR-트리는 데이터 분할 방법을 사용하기 때문에 데이터의 계속되는 위치 이동으로 인해 색인의 변경이 빈번히 발생하기 때문에 많은 갱신 시간이 요구한다. 이에 반해 제안하는 색인 구조는 공간 분할 방법을 사용하여 데이터를 색인하기 때문에 데이터 분할 방법을 사용하는 색인 구조의 문제점인 빈번한 색인 구조의 변경비용을 줄일 수 있고 보조색인 구조를 통한 빠른 객체의 검색을 지원함으로 갱신비용을 효율적으로 줄일 수 있다. 검색 성능은 10만개의 객체를 삽입하고 5~30분까지 미래 위치에 대한 범위 검색을 수행한다.
- 제안하는 색인 구조는 공간 분할 방식을 이용하여 색인을 구성하기 때문에 분할된 영역들 사이에 겹침이 발생하지 않으며 주 색인 구조의 중간 노드에는 자식 노드에 대한 속도정보를 저장하기 때문에 이동 객체의 미래 위치를 검색할 수 있다. 또한, 이동객체의 미래 위치를 검색하기 위해 불필요한 영역의 확장을 방지하기 위해 tesp을 이용하여 색인을 구성한다.
후속연구
- 실험을 통해 제안된 색인 구조는 기존 TPR-트리에 비해 갱신 및 검색 성능이 향상됨을 보였다. 향후 연구방향으로 색인 구조를 통한 다양한 질의 처리 기법에 대한 연구를 수행할 예정이다
※ AI-Helper는 부적절한 답변을 할 수 있습니다.