선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 본 논문에서는 도로 네트워크 공간에서 이동 객체의 현재 위치를 효율적으로 관리하기 위한 색인 구조를 제안하였다. 이를 위해, 교차점을 기반으로 도로망을 격자(grid)로 분할 및 도로의 연결 정보를 색인 구조에 통합하여 질의 처리 중에 사용할 수 있게 하였다.
- 본 논문에서는 위와 같은 문제점들을 해결하기 위해 이동 객체의 현재 위치를 효율적으로 저장할 수 있는 색인을 제안한다. 제안하는 색인은 빈번한 갱신 문제와 보조 색인의 유지비용 문제를 해결한 LUGrid[15]를 실세계에 적용할 수 있는 도로 네트워크 공간으로 확장하였다.
- 본 절에서는 제안 색인 구조에 대해 자세히 살펴본다.
제안 방법
- 제안 색인 구조에서 범위 질의(range query) 처리 알고리즘은 [표 1]과 같다. LUGrid의 범위 질의 처리 알고리즘을 도로의 연결 정보를 사용하도록 확장하였다. 먼저, 질의 영역(range)와 겹치는 메모리 격자(MG)의 집합 Setmg를 구한다(라인 2).
- 여기서, Grid Info는 선형눈금자(linear scale), IP는 교차점의 위치 정보, CP count는 총 연결점 수, CP List는 CP count만큼 저장된 연결점 정보이다. 그리고 LUGrid의 갱신 연산 처리 중에 발생하는 격자의 합병 및 분할을 방지하기 위해 해당 MG의 격자에서 사용하는 DG의 디스크 페이지의 수와 디스크 페이지에 포함되는 이동 객체의 정보를 추가하였다. 갱신되는 이동 객체의 가장 최근의 위치 정보만을 저장하는 MG의 각 격자에서 엔트리 수의 언더플로우(underflow)는 무시하고 오버플로우(overflow)가 발생하면 오버플로우 페이지를 추가 하여 사용한다([그림 8]-(4)).
- LUGrid에서 질의를 처리할 경우에는 먼저, 질의 범위(query range)와 MG의 격자 중에 겹침이 발생하는 격자들을 선별한 뒤, MG에 저장되어 있는 최신의 위치 정보 중에 질의 범위에 포함되는 것을 질의 결과 집합에 포함한다. 그리고 선별된 MG의 격자들에 대응되는 DG의 격자들을 한 개씩 읽어오면서 DG의 각 격자에 저장된 이동 객체의 위치 정보가 MDM에서 삭제대상으로 설정되어 있는 지와 질의 범위에 포함되는 지를 판단하여 질의 결과 집합에 포함하여 질의 처리를 종료한다. LUGrid의 경우, 대량의 이동 객체들이 군집하여 빠르게 이동할 경우에는 DG의 격자가 언더플로우와 오버플로우를 반복하게되어 DG와 MG의 합병과 분할이 많이 발생하게 되는 문제점과 도로망의 정보가 포함되어 있지 않은 MG와 질의 범위간의 겹침이 되는 범위에 대해 질의를 처리하여 질의 대상 범위가 넓다는 문제점이 존재한다.
- 또한, 도로의 연결 정보를 데이터 노드에 포함시켜 갱신 연산이나 검색 시에 이를 사용할 수 있게 하였다. 그리고 이동 객체의 갱신 연산 수행 시, 검색을 빠르게 처리하기 위해 이동 객체의 위치 정보를 저장한 데이터 노드 접근을 위한 해시 테이블을 구성하였다. IORN-tree는 모든 이동 객체에 대해 해시 테이블을 유지하는데 고비용이 소요된다는 문제점과 이동 객체의 위치가 다른 도로 세그먼트로 이동한 경우의 갱신 연산을 수행할 시, 저장될 새로운 도로 세그먼트를 찾기 위한 검색 비용 및 IMORS와 마찬가지로 갱신 연산을 한 개씩 처리한다는 문제점이 있다.
- 정적 색인은 도로망을 교차점을 기준으로 하여 폴리라인(poly line)으로 분할하여 도로 세그먼트를 만들고 R*-tree의 단말 노드(leaf node)인 MBR에 대응되는 로드 섹터 블록(Road sector block)으로 설정하여 해당 도로 세그먼트 위의 이동 객체들을 저장하였다. 그리고 이동 객체의 실제 위치 정보는 이동 객체 데이터 블록(data block for moving object)에 저장한 뒤, 갱신 시에 검색 비용을 줄이기 위해 로드 섹터 블록, 이동 객체 데이터 블록에 저장된 동일 이동 객체 간에 양방향 포인터를 두었다. IMORS의 갱신 정책에 의해 이동 객체의 위치 정보는 로드 섹터 블록을 벗어날 경우에만 검색 비용이 발생하게 된다.
- 첫 번째로 격자(grid) 기반의 도로 네트워크 모델을 제안한다. 두 번째로 LUGrid를 확장하여 격자의 분할 및 합병 문제를 해결하고 도로의 연결 정보를 사용하여 이동 객체의 검색 처리 성능을 향상시켰다. 또한, 건물과 같이 고정되어 있는 정적 객체 관리를 위한 색인 구조를 추가하여 질의를 처리할 경우 제안 색인에서 정적 객체 정보를 사용할 수 있도록 한다.
- 먼저, 본 논문에서 제안하는 색인 구조는 LUGrid[15]를 도로의 연결 정보를 포함하는 도로 네트워크 공간으로 확장하였고 갱신 연산중에 발생하는 합병 및 분할되는 문제점을 해결하였다. 또한, 건물, 병원, 주유소와 같은 POI(Point-Of-Interest)에 대한 검색을 처리할 수 있게 하기위한 색인 구조를 추가하였다.
- 분할한 도로 세그먼트들은 데이터 노드에 저장하고 데이터 노드들에 대해 R-tree를 구성한다. 또한, 도로의 연결 정보를 데이터 노드에 포함시켜 갱신 연산이나 검색 시에 이를 사용할 수 있게 하였다. 그리고 이동 객체의 갱신 연산 수행 시, 검색을 빠르게 처리하기 위해 이동 객체의 위치 정보를 저장한 데이터 노드 접근을 위한 해시 테이블을 구성하였다.
- 디스크의 버켓 페이지(bucket page)에 해당하는 디스크 격자(DG:Disk Grid)는 이동 객체의 위치 정보를 저장하고 있다. 또한, 해시 기반의 삭제 대상 메모(MDM:Miss-Deletion Memo)를 유지하여 삭제 대상이 되어 쓸모가 없게 된 위치 정보들(obsolete entries)을 저장한다. 그리고 MDM에 저장되는 삭제 대상 엔트리의 수를 제한하기 위해 특정 갱신 횟수에 도달하게 되면 Cleaner 수행하여 삭제 대상 위치 정보를 MG와 DG에 반영하게 한다.
- 그 뒤에, Setmg의 값을 한 개 씩 가져오면서 해당 격자 MGcell에 저장되어 있는 POI 색인의 단말 노드 포인터 정보를 가져온다(라인 4-8). 마지막으로 Setinput에 저장되어 있는 POI 색인 단말 노드 포인터를 하나 씩 가져오면서 단말 노드의 MBR이 질의 영역과 겹치는(overlap)지 확인하고 건물, 병원 등의 type과 비교하여 만족하는 단말 노드를 결과 집합에 포함한다.
- 먼저, 본 논문에서 제안하는 색인 구조는 LUGrid[15]를 도로의 연결 정보를 포함하는 도로 네트워크 공간으로 확장하였고 갱신 연산중에 발생하는 합병 및 분할되는 문제점을 해결하였다. 또한, 건물, 병원, 주유소와 같은 POI(Point-Of-Interest)에 대한 검색을 처리할 수 있게 하기위한 색인 구조를 추가하였다.
- 제안하는 색인의 갱신 연산은 LUGrid[15]의 연산을 확장하여 기존 기법에서 분할 및 합병 과정을 제거하였다. 분할 및 합병 과정을 제거하기 위해 MG의 격자(grid) 대응되는 DG의 격자에 오버플로우(overflow) 페이지를 추가할 수 있도록 확장하였다. 2.
- 본 논문에서는 도로 네트워크 공간에서 이동 객체의 현재 위치를 효율적으로 관리하기 위한 색인 구조를 제안하였다. 이를 위해, 교차점을 기반으로 도로망을 격자(grid)로 분할 및 도로의 연결 정보를 색인 구조에 통합하여 질의 처리 중에 사용할 수 있게 하였다. 기존 색인 기법을 갱신 연산중에 격자가 분할 및 병합이 되지 않도록 확장하였고 또한, 건물, 병원과 같은 정적 객체를 관리하는 색인을 따로 두어 질의 처리 시에 검색될 수 있게 하였다.
- IMORS[13]는 동적 색인(dynamic index)의 경우, 갱신 시에 중간 노드(internal node)가 합병과 분할을 반복하게 된다는 문제점과 도로는 거의 변하지 않는다는 점에 착안하여 색인을 정적 색인과 동적 색인으로 나누었다. 정적 색인은 도로망을 교차점을 기준으로 하여 폴리라인(poly line)으로 분할하여 도로 세그먼트를 만들고 R*-tree의 단말 노드(leaf node)인 MBR에 대응되는 로드 섹터 블록(Road sector block)으로 설정하여 해당 도로 세그먼트 위의 이동 객체들을 저장하였다. 그리고 이동 객체의 실제 위치 정보는 이동 객체 데이터 블록(data block for moving object)에 저장한 뒤, 갱신 시에 검색 비용을 줄이기 위해 로드 섹터 블록, 이동 객체 데이터 블록에 저장된 동일 이동 객체 간에 양방향 포인터를 두었다.
- Grid File에서는 메인 메모리 상에 해시 테이블과 같은 선형 눈금자(linear scale)를 두어 디스크의 해당 격자의 페이지 아이디(page id)를 저장하여 둔다. 제안 색인 구조는 이를 확장하여 메인 메모리 상에 MG에 격자 디렉토리(grid directory)와 도로 연결 정보 및 LUGrid에서 사용하는 속성 값을 저장한다. 이와 같이 구성할 경우의 이점은 Grid File의 분할된 격자를 이용하여 도로의 연결성을 확인할 수 있다.
- 본 논문에서는 위와 같은 문제점들을 해결하기 위해 이동 객체의 현재 위치를 효율적으로 저장할 수 있는 색인을 제안한다. 제안하는 색인은 빈번한 갱신 문제와 보조 색인의 유지비용 문제를 해결한 LUGrid[15]를 실세계에 적용할 수 있는 도로 네트워크 공간으로 확장하였다. 갱신 연산 비용을 줄인 LUGrid는 갱신 연산을 할 경우 격자(grid)에 저장되는 객체의 수에 따라 격자들이 합병(merge)되거나 분할(split)된다는 문제점과 주유소, 병원과 같이 움직임이 전혀 없는 정적 객체를 동적인 이동 객체와 같은 색인에서 관리를 하여 정적 객체의 위치가 변하지 않는다는 특성을 활용할 수 없다는 문제점이 있다.
- 제안하는 색인의 갱신 연산은 LUGrid[15]의 연산을 확장하여 기존 기법에서 분할 및 합병 과정을 제거하였다. 분할 및 합병 과정을 제거하기 위해 MG의 격자(grid) 대응되는 DG의 격자에 오버플로우(overflow) 페이지를 추가할 수 있도록 확장하였다.
- 본 논문의 장점은 다음과 같다. 첫 번째로 격자(grid) 기반의 도로 네트워크 모델을 제안한다. 두 번째로 LUGrid를 확장하여 격자의 분할 및 합병 문제를 해결하고 도로의 연결 정보를 사용하여 이동 객체의 검색 처리 성능을 향상시켰다.
대상 데이터
- 실험에 사용된 데이터 셋은 6105개의 노드와 7035개의 에지 및 교차점의 노드 수는 2238개이고 도로망의 크기는 23854 ×30851이다.
- 실험에 사용된 시스템의 하드웨어 및 소프트웨어 환경은 [표 3]과 같다. 실험에 사용된 데이터는 Brinkhoff가 제안한 데이터 생성기(Generating Network-Based Moving Object)[20, 21]를 사용하여 생성하였다. 실험에 사용된 데이터 셋은 6105개의 노드와 7035개의 에지 및 교차점의 노드 수는 2238개이고 도로망의 크기는 23854 ×30851이다.
- [그림 11]은 범위 질의(range query)에 대한 성능 평가이다. 이동 객체의 수는 총 10,000개이고 질의 대상 범위(range)는 전체 공간의 10%에서 90%에서 실험을 진행하였다.
이론/모형
- LUGrid[15]는 Grid File[19]을 기반으로 확장한 기법으로 갱신 연산이 삭제와 삽입으로 구성된다는 점에 착안하여 지연 삽입(Lazy-insertion)과 지연 삭제(Lazy-deletion) 기법을 적용하여 갱신 비용을 줄였다. Grid File과 다른 점은 격자 디렉토리(grid directory)를 디스크가 아니라 메모리에 유지한다는 점이다.
- 도로 네트워크는 도로망이 라인으로 표현되고 도로망이 교차하는 지점에서 교차점이 생성된다. 라인은 인접한 공간으로 뻗어 나가게 되는데 이와 같은 도로의 인접성을 표현하면서 LUGrid[15]를 도로 네트워크 공간 모델로 확장하기 위해 Grid 기반의 도로 네트워크 공간 모델을 사용하였다.
- 본 논문에서 제안하는 색인 구조의 우수성을 보이기 위해 기존의 색인 기법인 LUGrid[15]와 성능 평가를 수행한다. 실험에 사용된 시스템의 하드웨어 및 소프트웨어 환경은 [표 3]과 같다.
- 제안하는 도로 네트워크 공간 모델은 Grid File[19]을 기반으로 IRON-tree[14]에서 사용된 모델을 확장하였다. [그림 2]는 건물, 병원, 주유소와 같은 POI(Position-Of-Interest)가 포함된 실제 도로망이다.
성능/효과
- 2.2, 2.3 절에서 살펴본 바와 같이 이동 객체 환경에서의 색인은 대량의 이동 객체들의 갱신 연산 비용이 크다는 문제점과 빠른 검색을 위해 모든 이동 객체에 대한 보조 색인의 유지비용이 크다는 문제점을 가지고 있다. 이를 해결하기 위해 유클리드 공간 상에서 최소 갱신 비용 기법을 적용한 LUGrid[15]가 연구되었다.
- 또한, 건물과 같이 고정되어 있는 정적 객체 관리를 위한 색인 구조를 추가하여 질의를 처리할 경우 제안 색인에서 정적 객체 정보를 사용할 수 있도록 한다. 마지막으로 실험을 통해 기존의 색인보다 제안 색인의 성능이 우수함을 보인다.
- 기존 색인 기법을 갱신 연산중에 격자가 분할 및 병합이 되지 않도록 확장하였고 또한, 건물, 병원과 같은 정적 객체를 관리하는 색인을 따로 두어 질의 처리 시에 검색될 수 있게 하였다. 성능 평가 결과 제안 색인은 기존 기법보다 대량의 이동 객체에 대한 갱신 연산의 성능과 질의 처리 성능이 우수함을 확인할 수 있었다.
- 이동 객체의 수가 적을 경우, 제안 색인은 기존 색인 보다 갱신 성능이 조금 떨어지는 것을 알 수 있다. 하지만 이동 객체의 수가 증가 할수록 기존 기법보다 성능이 향상됨을 확인할 수 있다. 이와 같은 결과는 기존 LUGrid의 이동 객체 수가 증가 할수록 갱신 처리 중에 디스크 격자(DG)의 분할 및 합병의 수가 증가하게 되에 디스크 I/O가 증가하게 되지만 제안 색인은 오버플로우 페이지에 저장되어 있는 이동 객체의 위치 정보를 가져오기 위한 비용만이 추가되어 기존 색인보다 이동 객체의 증가에 따른 디스크 I/O 비용이 상대적으로 적기 때문이다.
후속연구
- 향후 연구로는 실험에서 확인된 문제점인 이동 객체 수에 따라 성능이 저하되는 문제점을 개선할 수 있는 연구가 필요하다. 이 문제점은 제안 색인 구조에서 이동 객체의 수에 따라 이동 객체의 위치 정보가 여러 디스크 페이지에 저장되어 발생하는 것이므로 도로의 폭, 너비에 의해 물리적인 이동 객체의 수가 제한된다는 점에 착안하여 분할된 도로 세그먼트가 저장할 수 있는 최대 객체 수까지 저장 가능한 효율적인 디스크 페이지 저장 기법을 연구하여 제안 색인 구조를 확장할 계획이다.
- 향후 연구로는 실험에서 확인된 문제점인 이동 객체 수에 따라 성능이 저하되는 문제점을 개선할 수 있는 연구가 필요하다. 이 문제점은 제안 색인 구조에서 이동 객체의 수에 따라 이동 객체의 위치 정보가 여러 디스크 페이지에 저장되어 발생하는 것이므로 도로의 폭, 너비에 의해 물리적인 이동 객체의 수가 제한된다는 점에 착안하여 분할된 도로 세그먼트가 저장할 수 있는 최대 객체 수까지 저장 가능한 효율적인 디스크 페이지 저장 기법을 연구하여 제안 색인 구조를 확장할 계획이다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.