R*-Tree와 Grid를 이용한 이동 객체의 위치 일반화 기법 = Location Generalization Method of Moving Object using R*-Tree and Grid

국문 초록 (Abstract)

패턴 탐사에 관한 기존의 연구들[1,2,3,4,5,6,11,12,13]은 이동 객체의 위치 이력 데이터 집합에 대한 위치 일반화 접근법을 사용하지 않거나 사용해도 특정 공간상의 이동 패턴들 중 단순히 시공간 제약이 없는 빈발패턴만을 추출하므로, 특정 지점들 간의 최적 이동 경로나 스케줄링 경로와 같은 시공간 제약을 갖는 빈발 패턴탐사에는 적용하기 어렵다. 또한 패턴 탐사의 수행에 있어 기존의 기법들은 데이터베이스에 대한 반복 접근을 줄이기 위해 메모리 상에 패턴 트리를 생성하여 사용하므로 보다 많은 메모리 공간을 소요하게 된다. 따라서 이러한 기존 탐사 기법들의 문제점들을 해결하기 위한 보다 효율적인 패턴 탐사 기법이 필요한 실정이다. 효율적 탐사 기법을 개발하기 위하여 본 논문에서는 방대한 이동 객체의 이력 데이터 집합에 대한 탐사 수행 시간 및 탐사에 필요한 메모리 공간을 최소화하기 위해서 상세 수준의 데이터들을 의미있는 공간영역 정보로 변환하는 새로운 위치 일반화 방법을 제안한다. 제안된 방법은 패턴 탐사의 전처리 과정에서 R*-Tree와 영역 Grid 해쉬테이블(AGHT:Area Grid Hash Table)을 기반으로 이동 객체의 위치 속성들을 2차원 공간영역으로 일반화하여 이동 시퀀스를 생성함으로써 효율적인 이동 객체의 공간 이동 패턴 마이닝을 유도할 수 있다.

다국어 초록 (Multilingual Abstract)

The existing pattern mining methods[1,2,3,4,5,6,11,12,13] do not use location generalization method on the set of location history data of moving object, but even so they simply do extract only frequent patterns which have no spatio-temporal constraint in moving patterns on specific space. Therefore, it is difficult for those methods to apply to frequent pattern mining which has spatio-temporal constraint such as optimal moving or scheduling paths among the specific points, And also, those methods are required more large memory space due to using pattern tree on memory for reducing repeated scan database. Therefore, more effective pattern mining technique is required for solving these problems. In this paper, in order to develop more effective pattern mining technique, we propose new location generalization method that converts data of detailed level into meaningful spatial information for reducing the processing time for pattern mining of a massive history data set of moving object and space saving. The proposed method can lead the efficient spatial moving pattern mining of moving object using by creating moving sequences through generalizing the location attributes of moving object into 2D spatial area based on R*-Tree and Area Grid Hash Table(AGHT) in preprocessing stage of pattern mining.

목차 (Table of Contents)

• 요약
• Abstract
• Ⅰ. 서론
• Ⅱ. 관련연구
• Ⅲ. 이동 객체와 공간 개념 계층
• Ⅳ. 이동 객체의 위치 일반화
• Ⅴ. 실험 및 성능평가
• Ⅵ. 결론 및 향후 연구과제
• 참고문헌
• 저자소개

참고문헌 (Reference)

1 이준욱, "지식 탐사 프레임워크 기반의 시공간 이동 패턴 탐사 기법" 충북대학교 대학원 2003

2 이준욱, "이동객체 위치 일반화를 이용한 시공간 이동 패턴 탐사" 한국정보처리학회 10 (10): 1103-1114, 2003

3 박지웅, "시공간 이동 패턴 추출을 위한 효율적인 알고리즘" 건국대학교 대학원 2006

4 J. W. Lee, "Temporal moving pattern mining for location-based service" 73 : 2004

5 J. D. Chung, "Temporal Pattern Mining of Moving Objects for Location-Based Service" 2002

6 J. Moreira, "Representation and Manipulation of Moving Points : An Extended Data Model for Location Estimation" 26 (26): 1999

7 S. Ramaswamy, "On the discovery of interesting patterns in association rules" 1998

8 N. Mamoulis, "Mining, Indexing, and Querying Historical Spatio-Temporal Data" 2004

9 R. Srikant, "Mining sequential patterns : Generalizations and Performance Improvements" Springer-verlag 1996

10 R. Agrawal, "Mining sequential patterns" 1995

11 P. Stolotz, "Fast Spatio- Temporal Data Mining of Large Geophysical Datasets" 1995

12 E. Tsoukatos, "Efficient Mining of Spatio-Temporal Patterns" 425-442, 2001

13 J. Han, "Efficient Mining of Partial Periodic Patterns in Time Series Database" 1999

14 H. Manniila, "Discovery of frequent episodes in event sequences" 1 (1): 259-289, 1997