이동 시퀀스 트리를 이용한 효율적인 시공간 이동 패턴 탐사 기법
The Efficient Spatio-Temporal Moving Pattern Mining using Moving Sequence Tree
2
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
최근 이동 객체의 동적인 위치나 이동성에 기반하여 여러 분야에 적용가능한 위치 기반 서비스를 개발하고자 다양한 객체의 이동 패턴들로부터 유용한 패턴을 추출하기 위한 패턴 탐사 기법에 대한 연구가 활발히 진행되고 있다. 이동 패턴 탐사는 특성상 방대한 시공간 데이터의 분석 및 처리 방법에 따라 패턴 탐사의 성능이 좌우된다. 기존의 시공간 패턴 탐사 기법들[1-6,8-11] 중 일부는 이러한 문제를 해결하기 위한 방법을 제시하였으나, 패턴 탐사 수행 시간이나 패턴 탐사 시 사용되는 메모리양을 최소화하는데 있어 아직 부족한 실정이다. 이에 본 논문에서는 방대한 시공간 이동 데이터 집합으로부터 순차적이고 주기적인 빈발 이동 패턴을 효과적으로 추출하기 위한 새로운 시공간 이동 패턴 탐사 기법을 제안한다. 제안된 기법에서는 이동 객체의 이력 데이터로부터 해시 트리 기반의 이동 시퀀스 트리를 생성하여 빈발 이동 패턴을 탐사함으로써 탐사 수행 시간을 83%∼93% 감소시키고, 시간 및 공간 속성을 가진 상세 수준의 이력 데이터들을 공간 및 시간 개념 계층을 이용하여 실세계의 의미있는 시간 및 공간영역으로 일반화함으로써 탐사 시 소요되는 메모리양을 감소시켜 보다 효과적인 패턴 탐사를 유도한다.
Abstract
Recently, based on dynamic location or mobility of moving object, many researches on pattern mining methods actively progress to extract more available patterns from various moving patterns for development of location based services. The performance of moving pattern mining depend on how analyze and process the huge set of spatio-temporal data. Some of traditional spatio-temporal pattern mining methods[1-6,8-11]have proposed to solve these problem, but they did not solve properly to reduce mining execution time and minimize required memory space. Therefore, in this paper, we propose new spatio-temporal pattern mining method which extract the sequential and periodic frequent moving patterns efficiently from the huge set of spatio-temporal moving data. The proposed method reduces mining execution time of 83%∼93% rate on frequent moving patterns mining using the moving sequence tree which generated from historical data of moving objects based on hash tree. And also, for minimizing the required memory space, it generalize the detained historical data including spatio-temporal attributes into the real world scope of space and time using spatio-temporal concept hierarchy.
참고문헌 (15)
- D. O. Kim, "STMPE : An Efficient Movement Pattern Extraction Algorithm for Spatio-temporal Data Mining", proc. on International Conference on Computational Science and Its Applications(ICCSA), pp.259~269 (2006)
- N. Mamoulis, "Mining, Indexing and Querying Historical Spatio-Temporal Data", proc. on the International Conference on Knowledge Discovery and Data Mining (2004)
- H. Cao, "Mining Frequent Spatio-Temporal Sequential Patterns", proc. on the 5th IEEE International Conference on Data Mining(ICDM), pp.82~89 (2005)
- Y. Huang, "Finding Sequential Patterns from a Massive Number of Spatio-Temporal Events" (2006), SDM, SIAM
- J. W. Lee, "Temporal Moving Pattern Mining for Location-Based Service", The Journal of Systems and Software, 73 (2004)
- G. Yavas, "A Data Mining Approach for Location Prediction in Mobile Environmensts", Data & Knowledge Engineering, 54, pp.121~146 (2005)
- J. Allen, "Maintaining Knowledge about Temporal Intervals", Comm. of the ACM, 26(11) (1983)
- 백옥현, "위치 기반 서비스를 위한 이동 객체의 시간 패턴 탐사 기법", 석사, pp.2002
- 이준욱, "위치 기반 서비스를 위한 이동 객체의 시간 패턴 탐사 기법", 정보과학회논문지 : 데이타베이스, 29(5), pp.335~346 (2002), 한국정보과학회
- 이준욱, "지식 탐사 프레임워크 기반의 시공간 이동 패턴 탐사 기법", 박사, pp.2003
- 한선영, "시공간 이동 시퀀스 패턴 마이닝 기법", 석사, pp.2006
- 박지웅, "시공간 이동 패턴 추출을 위한 효율적인 알고리즘", 박사, pp.2006
- 고 현, "최적 경로 서비스 지원을 위한 이동 객체의 이동 패턴 탐사 알고리즘", 한국정보처리학회 추계학술발표대회논문집, 7(2) (2006)
- 고 현, "이동 객체의 패턴 마이닝을 위한 위치 일반화 방법", 한국정보처리학회 추계학술발표대회논문집, 7 (2006)
- 고현, "이동 객체의 패턴 탐사를 위한 시공간 데이터 일반화 기법", 한국정보과학회 한국컴퓨터종합학술대회논문집(C), 34(1) (2007)