모바일 응용에서 이동 객체의 궤적-기반 질의를 위한 색인 구조 = An Index Structure for Trajectory-based Query of Moving Objects in Mobile Applications

다국어 초록 (Multilingual Abstract)

With the rapid development of wireless communications and mobile technologies, requirements of various services based on moving objects like location-based services and mobile applications services have been increased. In this paper, we propose an index structure which can improve the performance on trajectory-based query especially, one of the various query types for moving objects in mobile applications. It maintains link table(L-Table) to obtain good efficiency on retrieval and insertion performance of the existing TB(Trajectory Bundle)-tree proposed for trajectory-based query of moving objects. The L-Table contains page number in disk and memory pointers pointing the leaf node with the first and last line segment of moving objects in order to directly access preceding node. In addition, we design to reside a part of whole index in main memory by preserving a fixed size of buffer in case of being restricted by available main memory. Finally, experimental results with various data sets show that the proposed technique is superior to the existing index structures with respect to insertion and trajectory-based query.

국문 초록 (Abstract)

무선 통신 및 모바일 기술의 급속한 발전으로 인해 위치 기반 서비스 및 모바일 응용 서비스와 같은 이동 객체에 기반한 다양한 서비스에 대한 요구가 증가하게 되었다. 이를 위해, 본 논문에서는 모바일 응용에서 이동 객체에 대한 다양한 질의 중에서 특히 궤적-기반 질의에 대한 성능을 향상시킬 수 있는 색인 구조를 제안한다. 제안하는 색인 구조는 이동 객체의 궤적-기반 질의를 위해 제안되었던 기존의 TB-tree의 삽입 및 검색 성능의 효율성을 높이기 위해 연결테이블(LinkTable:L-Table)을 유지한다. L-Table은 선행 노드를 한번에 직접 접근하기 위해 이동 객체의 처음 세그먼트와 마지막 세그먼트가 저장된 단말 노드를 가리키는 포인터 정보와 디스크에서의 페이지를 가리키는 페이지 번호를 저장한다. 아울러 시스템의 가용메모리가 제약을 받는 경우에도 일정한 크기의 버퍼를 유지해 색인의 일부만을 메모리에 상주시킬 수 있도록 설계한다. 마지막으로 제안하는 색인 구조의 성능을 평가하기 위하여 다양한 실험 데이타를 이용해 성능 평가를 수행한 결과, 삽입 및 궤적-기반 질의 측면에서 기존의 색인 구조들에 비해 더 나은 성능을 보인다.

참고문헌 (Reference)

1 "이동체를 위한 궤적 색인의 분할 정책" 5 (5): 173-176, 2002.

2 "시공간 질의를 위한 인덱싱 기법" 18 (18): 93-100, 2002.

3 "On the generation of spatiotemporal datasets" 147-164, 1999.

4 "Novel Approaches in Query Processing for Moving Objects" 395-406, 2000.

5 "Moving objects databases: Issues and solutions" 111-122, 1998.

6 "MV3R-Tree: A Spatio- Temporal Access Method for Timestamp and Interval Queries" 431-440, 2001.

7 "Indexing the Positions of Continuously Moving Objecs" 331-342, 2000.

8 "Indexing the Current Positions of Moving Objects Using the Lazy Update R-Tree" 113-120, 2002.

9 "Indexing Trajectories in Query Processing for Moving Objects" 1999.

10 "An Efficient and Robust Access Method for Points and Rectangles In Proc. of ACM SIGMOD" 302-331, 1990.

11 "A Framework for Generating Network-Based Moving Objects" 6 (6): 153-180, 2002.