As the area of location aware devices, such as GPS, PDAs, advance and are widely used recently, large amount of data are collected in the form of trajectories. Therefore, management for the trajectory data becomes important. This paper considers convoy query in trajectory databases. Convoy is a group of objects that have similar movements for some amounts of time in the history. A group of animals migrating or convoys of vehicles can be examples. Discovering convoys is related to analyzing pattern of movements for ani-mals or analysis for traffic control.
Efficient and effective querying for convoys require two-phase steps. In the first step, simplification using minimum description length (MDL) principle is performed on trajectories for efficient convoy discovery. Using MDL principle for trajectories simplification rather than other line simplification methods, more accurate convoy discovery can be achieved. Density-based line clustering on simplified trajectories is per-formed in the second step. Density-based clustering makes it possible for clusters to have random shapes and extents. Experiments with real and synthetic trajectory datasets show that the proposed approach is accurate.
GPS, PDA 같은 여러 모바일 장치들의 위치 인식 기능이 가능해지면서, 움직이는 물체들의 시공간적 위치 정보를 기록해 놓은 경로 데이터베이스에 대한 관리에 대한 필요성이 증가하고 있다. 이 논문에서는 경로 데이터들에 대한 집단(convoy)을 찾은 질의를 다룬다. 집단(convoy)란 일정 시간 동안 함께 이동한 물체들의 모임이다. 이동하는 동물들의 집단이나 자동차들의 이동 등을 예로 들 수 있다. 집단 발견에 대한 질의는 관심 있는 물체들에 대한 패턴 분석이나 교통 처리 계획, 동물들의 행동 분석 등과 관련이 있다.
정확하고 효율적인 질의를 위한 알고리즘은 두 가지 단계로 되어 있다. 첫 번째 단계에서는 보다 효율적인 집단 발견을 위해 최소 묘사 길이(minimum description length) 원리를 이용한 경로 단순화를 수행한다. 최소 묘사 길이 원리를 이용함으로써 기존의 경로 단순화 방법들보다 정확한 결과를 얻을 수 있다. 두 번째 단계에서는 단순화된 경로들을 밀돈 기반의 선 클러스터링을 수행한다. 밀도 기반 클러스터링을 적용해 임의의 모양과 범위를 갖는 집단(convoy)를 찾을 수 있다. 실제 및 가상의 경로 데이터에 대한 실험 결과를 통해 방법이 효과적임을 볼 수 있다
