효율적인 시공간 영역 질의 처리를 위한 궤적 색인의 노드 재배치 전략

임덕성(Duksung Lim),조대수(Daesoo Cho),홍봉희(Bonghee Hong) 한국정보과학회 2004 정보과학회논문지 : 데이타베이스 Vol.31 No.6

The trajectory preservation property that stores only one trajectory in a leaf node is the most important feature of an index structure, such as the TB-tree for retrieving object's moving paths in the spatio-temporal space. It performs well in trajectory-related queries such as navigational queries and combined queries. But, the MBR of non-leaf nodes in the TB-tree have large amounts of dead space because trajectory preservation is achieved at the sacrifice of the spatial locality of trajectories. As dead space increases, the overlap between nodes also increases, and, thus, the classical range query cost increases. We present a new split policy and entry relocation policies, which have no deterioration of the performance for trajectory-related queries, for improving the performance of range queries. To maximally reduce the dead space of a non-leaf node's MBR, the Maximal Area Reduction (MAR) policy is used as a split policy for non-leaf nodes. The entry relocation policy induces entries in non-leaf nodes to exchange each other for the purpose of reducing dead spaces in these nodes. We propose two algorithms for the entry relocation policy, and evaluate the performance studies of new algorithms comparing to the TB-tree under a varying set of spatio-temporal queries. TB-tree와 같이 시공간에서 궤적 검색을 위한 색인 구조는 단말 노드에 하나의 궤적만을 저장하는 궤적 보존의 특성을 가지기 때문에 궤적의 일부분을 추출하는 항해 질의(Navigational Query)에서 우수한 성능을 보인다. 그러나, 궤적 보존을 위해 공간적 지역성을 완전히 배제하는 구조를 가짐으로써 비단말 노드의 MBR(Minimum Bounding Rectangle)은 큰 사장 영역을 가지는 단점이 있다. 사장 영역 증가는 노드간의 중첩을 높이는 원인을 제공하기 때문에 영역 질의의 성능을 저하시키는 문제가 있다. 이 논문에서는 궤적 검색을 위한 색인 구조에서 항해질의 성능을 유지하면서 영역 질의의 성능을 향상 시키기 위한 비단말 노드 분할 정책과 엔트리 재배치 정책을 제시한다. 분할 정책은 비단말 노드의 분할 시 비단말 노드의 MBR을 최대한 감소시키는 최대 영역 축소(Maximal Area Reduction) 정책을 사용하고, 엔트리 재배치 정책은 비단말 노드를 구성하는 다수의 엔트리에서 MBR을 최대로 감소시킬 수 있는 엔트리의 위치를 재배치시키는 방법으로 이 논문에서는 분할 방법에 따라 2가지 재배치 전략을 제시하고 TB-tree와 성능을 비교한다.

이동체 데이타베이스에서 복합 질의를 위한 궤적 분할 트리의 설계 및 구현

임덕성(Duksung Lim),전봉기(Bonggi Jun),홍봉희(Bonghee Hong),조대수(Dae-Soo Cho) 한국정보과학회 2004 정보과학회논문지 : 데이타베이스 Vol.31 No.2

이동체는 시간에 따라 위치를 변경하는 특성과 이동체의 경로는 궤적으로 표현되는 특성을 가진다. 이동체 궤적 데이타에 대한 저장 및 검색을 처리하는 이동체 데이타베이스 시스템에서는 효율적인 데이타 접근 방법이 필요하다. 특히 궤적 검색을 위한 대표적인 질의 유형인 복합 질의는 영역내의 궤적 검색과 궤적의 일부분을 추출하는 과정을 포함한다. 그러나, 영역 질의에 우수한 색인 방법은 부분 궤적을 추출하기 위한 비용이 높은 단점을 가진다. 반면, 궤적 질의를 위한 색인 방법의 경우 노드 간의 중첩이 매우 높아 영역내의 궤적 검색 비용이 높은 단점이 있다. 이 논문에서는 이동체 데이타베이스에서 복합 질의를 효율적으로 처리하기 위해 TR-tree를 제시한다. TR-tree는 궤적 질의를 위해 궤적 보존 및 단말 노드의 용량을 증가시키고, 영역 질의 처리를 위해 사장영역과 MBB(Minimum Bounding Box)의 중첩을 감소시키는 논리적 궤적 분할을 지원하는 특징을 가진다. 실험 평가에서 TR-tree는 STR-tree, TB-tree의 복합 질의 성능 비교에서 평균 25%의 노드 접근 회수를 감소시킨다. Moving objects have characteristics that they change continuously their positions over time. The movement of moving objects should be stored on trajectories for processing past queries. Moving objects databases need to provide spatio-temporal index for handling moving objects queries like combined queries. Combined queries consist of a range query selecting trajectories within a specific range and a trajectory query extracting to parts of the whole trajectory. Access methods showing good performance in range queries have a shortcoming that the cost of processing trajectory queries is high. On the other hand, trajectory-based index schemes like the TB-tree are not suitable for range queries because of high overlaps between index nodes. This paper proposes new TR(Trajectory Riving)-tree which is revised for efficiently processing the combined queries. This index scheme has several features like the trajectory preservation, the increase of the capacity of leaf nodes, and the logical trajectory riving in order to reduce dead space and high overlap between bounding boxes of nodes. In our performance study, the number of node access for combined queries in TR-tree is about 25% less than the STR-tree and the TB-tree.

이동 객체 데이타베이스에서 KDB-tree의 동적 분할 정책

임덕성(Duksung Lim),이창헌(Changheun Lee),홍봉희(Bonghee Hong) 한국정보과학회 2006 정보과학회논문지 : 데이타베이스 Vol.33 No.4

Moving object databases manage a large amount of past location data which are accumulated as the time goes. To retrieve fast the past location of moving objects, we need index structures which consider features of moving objects. The KDB-tree has a good performance in processing range queries. Although we use the KDB-tree as an index structure for moving object databases, there has an over-split problem in the spatial domain since the feature of moving object databases is to increase the time domain. Because the over-split problem reduces spatial regions in the MBR of nodes inverse proportion to the number of splits, there has a problem that the cost for processing spatial-temporal range queries is increased. In this paper, we propose the dynamic split strategy of the KDB-tree to process efficiently the spatial-temporal range queries. The dynamic split strategy uses the space priority splitting method for choosing the split domain, the recent time splitting policy for splitting a point page to maximize the space utilization, and the last division policy for splitting a region page. We compare the performance of proposed dynamic split strategy with the 3DR-tree, the MV3R-tree, and the KDB-tree. In our performance study for range queries, the number of node access in the MKDB-tree is average 30% less than compared index structures. 시간의 흐름에 따라 누적되는 대용량의 과거 위치를 관리하는 이동 객체 데이타베이스에서 이동 객체의 과거 위치를 효율적으로 검색하기 위해서는 이동 객체의 특성을 고려한 색인 구조가 필요하다. 그러나, 영역 질의 성능이 우수한 다차원 색인인 KDB-tree를 이동 객체 데이타베이스에 적용할 경우 시간 도메인이 증가하는 이동 객체 데이타베이스의 특성으로 인해 공간 도메인 가중 분할이 발생한다. 공간도메인 가중 분할은 하나의 노드가 차지하는 MBR의 공간 영역이 분할 횟수에 반비례하게 감소되어 시공간 영역 질의 처리시 색인의 검색 비용을 증가시키는 문제가 있다. 이 논문에서는 이동 객체 데이타베이스에서 시공간 영역 질의를 효율적으로 처리하기 위한 KDB-tree의 동적 분할 정책을 제안한다. 동적 분할 정책은 공간 우선 분할 방법을 적용하는 분할 도메인 선정 방법과 포인터 페이지에서 공간 활용도를 최대화 시킬 수 있는 최근 시간 분할 정책, 영역 페이지에서 적용되는 최후 시간 분할 정책으로 구성된다. 제안한 동적 분할 정책의 성능을 평가하기 위해 3DR-tree, MV3R-tree, KDB-tree와의 성능을 비교한다. 영역 질의를 위한 성능 평가에서 동적 분할 정책을 적용한 MKDB-tree는 기존 색인에 비해 평균 30%이상의 노드 접근 회수를 감소시킨다.

RFID/LBS 환경에서 태그 이동 객체의 위치 추적을 위한 색인 구조

안준환(Junhwan An),임덕성(Duksung Lim),안성우(Sungwoo Ahn),홍봉희(Bonghee Hong) 한국정보과학회 2006 한국정보과학회 학술발표논문집 Vol.33 No.1

RFID를 이용하는 물류 시스템에서 태그 객체의 위치 추적을 위해서는 태그 객체의 궤적을 모델링하고 효율적으로 검색하기 위한 색인 구성이 필수적이다. 태그 객체의 궤적은 리더의 인식 영역에 들어오고 나가는 두 점을 연결한 시공간 선분으로 표현할 수 있다. 그러나 태그 객체가 리더의 인식영역 밖으로 벗어나게 되면 태그 객체의 궤적을 표현할 수 없으므로 위치 추적이 불가능하게 되는 문제를 가진다. 이러한 문제를 해결하기 위하여 리더의 비 인식 영역에서 GPS를 이용한 태그 객체의 위치 추적을 병행할 필요가 있다. 본 논문에서는 RFID 시스템과 LBS 시스템을 연동한 환경에서 태그 궤적을 표현하기 위한 위치 추적 시스템의 모델을 제시하고, 제시된 모델에서 태그 객체의 위치 추적을 효율적으로 처리하기 위한 색인 구조를 제안한다. 제안된 색인 구조는 태그 객체의 현재 위치뿐만 아니라 과거 궤적을 효율적으로 처리하기 위한 새로운 삽입 및 분할 알고리즘을 제안하여 노드가 차지하는 영역을 최소화한다.

시공간 근접성을 고려한 TB - tree의 동적 삽입 정책

장종우(Jongwoo Chang),임덕성(Duksung Lim),홍봉희(Bonghee Hong) 한국정보과학회 2003 한국정보과학회 학술발표논문집 Vol.30 No.1A

이동체 데이터베이스에서 대용량 궤적 정보를 효율적으로 검색하기 위해서는 색인이 필요하다. 특히 궤적을 선택하는 과정과 선택된 궤적의 일부분을 추출하는 과정으로 이루어진 복합 질의를 효율적으로 처리하기 위해서는 궤적 보존을 지원하는 TB-tree와 같은 색인 구조가 적합하다. 그러나, TB-tree는 공간적인 인접성을 고려하지 않아 비단말 노드의 겹침과 사장 영역이 매우 커 영역 질의의 비용이 증가하는 문제가 있다. 이 논문에서는 복합 질의 및 영역 질의를 효율적으로 처리하기 위하여, TB-tree에서 사장 영역을 감소시킬 수 있는 최대 영역 감소 정책을 제시한다. 최대 영역 감소 정책은 공간 활용도를 최대로 유지하면서 사장 영역을 점진적으로 감소시키는 삽입 및 분할 정책으로서 TB-tree의 비단말 노드의 겹침을 줄여 영역 질의의 비용을 감소시킨다.

주기적인 위치 보고 이동체의 불확실 위치 처리

진희규(Heegyu Jin),김동현(Donghyun Kim),임덕성(Duksung Lim),홍봉희(Bonghee Hong) 한국정보과학회 2004 한국정보과학회 학술발표논문집 Vol.31 No.2Ⅱ

위치기반서비스 응용 분야에서 위치 데이터를 저장하기 위하여 일반적으로 이동체의 위치 데이터를 주기적으로 수집한다. 주기적으로 수집된 위치 데이터는 보고 주기 사이의 위치 변화를 반영하지 못하기 때문에 시간에 대한 선형 함수를 이용하여 예측된 위치 데이터와 오차가 발생한다. 따라서 오차가 존재하는 불확실한 미래 위치 데이터로 인하여 미래 위치 색인에서 검색의 정확도가 떨어지는 문제점이 발생한다. 이 논문에서는 주기적인 위치 보고 이동체에서 발생하는 불확실한 위치 데이터를 처리하기 위해서 예측된 위치 데이터 예측 오차분을 반영한 불확실성 영역을 사용한다. 그리고 이동체의 불확실성 영역을 설정하기 위하여 최근 예측 오차 가중치 기법과 칼만 필터 기법을 제안하고 이를 기반으로 하는 불확실 위치 처리 기법을 이동체 미래 위치 색인에서 구현하고 성능 비교 평가를 수행한다. 성능 평가 결과에 따르면 기존의 선형함수 기반 예측 기법보다 불확실 위치 처리 기법이 영역 검색의 정확도가 향상되는 장점을 가진다.

텔레매틱스를 위한 불확실성 기반의 이동체 색인

진희규(Heegyu Jin),김동현(Donghyun Kim),임덕성(Duksung Lim),조대수(Daesoo Cho),홍봉희(Bonghee Hong) 한국정보과학회 2004 한국정보과학회 학술발표논문집 Vol.31 No.1B

속도와 방향이 바뀔 때 마다 이동체의 위치를 보고하는 TPR-tree는 이동체의 위치를 예측하는 오차가 적다. 그러나 긴 시간 간격으로 이동체의 위치를 보고하면 위치 예측의 불확실성이 높아져서 위치 예측의 오차 값이 증가한다. 불확실성이 높은 이동체를 TPR-tree에 적용할 때 이동체의 위치 정보를 갱신하기 위한 색인 검색 비용이 증가하고, 질의 결과의 정확도가 낮아지는 문제가 발생한다. 이 논문에서는 긴 시간 간격으로 이동체 위치를 보고할 때 발생하는 이동체 위치의 불확실성을 고려하기 위해서 불확실성 영역(uncertainty region)을 이용한 확장 TPR-tree를 제시한다. 불확실성이 높은 이동체의 위치 데이터를 처리하기 위해서 이동체의 이동 가능한 영역을 위치 예측의 오차 값을 이용하여 계산한 불확실성 영역을 설정하고, 검색을 위하여 노드의 BR을 계산할 때 불확실성 영역을 이용하여 BR을 확장한다.

전자태그 객체의 추적을 위한 간격 R - 트리의 분할 정책

이세호(Seho Lee),안성우(Sungwoo Ahn),홍봉희(Bonghee Hong),반재훈(Chaehoon Ban),임덕성(Duksung Lim) 한국정보과학회 2005 한국정보과학회 학술발표논문집 Vol.32 No.1

RFID(Radio Frequency Identification)는 자동 인식 데이터 수집 장치의 한 분야로써 GPS장치를 장착한 차량과 같이 , RFID 태그(전자태그)를 상품에 부착하여 인식, 추적할 수 있다. 이러한 전자태그 객체는 시간에 따라 경로 정보가 누적되는 이동체와 유사한 특성을 가진다. 그러나 기존의 이동체 색인과 달리 태그 객체의 위치는 판독기의 위치로 인식되며 위치보고가 판독기의 인식영역 안에서만 이루어지므로 보고 주기를 예측할 수 없다. 기존의 이동체 색인에서 전자태그의 특성을 표현하기 힘들기 때문에 전자태그의 특성을 고려한 색인이 필요하게 되었다. 최근 전자태그의 특성을 고려한 색인인 TPIR-Tree(Time parameterized Interval R-Tree)가 발표되었다 그러나 이 색인은 기존 공간 색인에서의 균등분할 기법을 사용하여 위치보고가 시간의 순서를 가지는 전자태그의 특성을 고려하지 못하여 과거노드의 저장효율이 좋지 못하다. 이 논문에서는 TPIR-Tree의 저장효율 및 검색 성능 향상을 위해서 시간의 순서에 따라 위치를 보고하는 전자태그 객체의 특성을 고려하여 분할축 선정 기법 및 시간축 분할시 비균등 분할정책을 제안한다.