공간 네트워크 상의 이동객체를 위한 시그니처 기반의 궤적 색인구조 (Trajectory Index Structure based on Signatures for Moving Objects on a Spatial Network)

서지정보

· 발행기관 : 한국공간정보시스템학회
· 수록지 정보 : 한국공간정보시스템학회 논문지 / 10권 / 3호 / 1 ~ 18페이지
· 저자명 : 김영진, 김영창, 심춘보, 장재우

초록

공간 네트워크 상을 움직이는 많은 이동객체들의 궤적 분석을 통해서 많은 정보를 얻을 수 있다. 이를
위해서, 궤적을 효과적으로 검색할 수 있는 궤적 기반 색인 구조가 필요하다. 하지만 도로와 같은 공간 네트
워크상의 궤적 기반 색인 구조에 대한 연구는 FNR-트리나 MON-트리를 제외하고는 연구가 많이 부족한
실정이다. 또한, FNR-트리나 MON-트리는 에지를 지난 이동객체의 이동정보인 세그먼트만을 저장할
뿐 전체 궤적을 유지하지 못하며, 궤적 질의에 대해 비효율적이다. 따라서 본 논문에서는 공간 네트워크상
의 이동객체를 위한 시그니처 기반의 궤적 색인 구조인 SigMO-트리를 제안한다. 이를 위해, 이동객체를
공간과 시간 특성으로 분류하고, 전체 궤적을 유지함으로써 영역질의와 궤적질의를 동시에 처리할 수 있는
색인 구조를 설계한다. 아울러, 사용자 질의를 시공간영역 내 궤적 질의, 시간영역 내 유사궤적 질의로 분
류하고, 이들을 처리하기 위한 질의 처리 알고리즘을 제안한다. 각 질의처리 알고리즘은 효율적인 검색을
위하여 시그니처 파일 기법을 이용하여 궤적을 검색한다. 마지막으로 성능평가를 통해 본 논문에서 제안한
궤적 기반 색인 구조가 기존의 색인구조인 FNR-트리, MON-트리보다 성능이 우수함을 보인다.

영어초록

Because we can usually get many information through analyzing trajectories of moving
objects on spatial networks, efficient trajectory index structures are required to achieve good
retrieval performance on their trajectories. However, there has been little research on
trajectory index structures for spatial networks such as FNR-tree and MON-tree. Also,
because FNR-tree and MON-tree store the segment unit of moving objects, they can't
support the trajectory of whole moving objects.In this paper, we propose an efficient trajectory index structures based on signatures on a
spatial network, named SigMO-Tree. For this, we divide moving object data into spatial and
temporal attributes, and design an index structure which supports not only range query but
trajectory query by preserving the whole trajectory of moving objects. In addition, we divide
user queries into trajectory query based on spatio-temporal area and similar-trajectory
query, and propose query processing algorithms to support them. The algorithm uses a
signature file in order to retrieve candidate trajectories efficiently Finally, we show from our
performance analysis that our trajectory index structure outperforms the existing index
structures like FNR-Tree and MON-Tree.

참고자료

· 없음