이산 프레셰 거리 척도를 이용한 궤적 유사도 고속계산 휴리스틱 알고리즘 (Fast Heuristic Algorithm for Similarity of Trajectories Using Discrete Fréchet Distance Measure)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회 컴퓨팅의 실제 논문지 / 22권 / 4호 / 189 ~ 194페이지
· 저자명 : 박진관, 김태용, 박보국, 조환규

초록

궤적은 이동체가 움직인 경로이다. IT 기술의 성장은 GPS와 같은 위치 측정 장치를 통해 다양한 이동체의 궤적 데이터를 수집할 수 있게 하였다. 이동체의 궤적은 지리정보시스템(GIS)을 포함한 다양한 연구 분야에서 사용된다. 지리정보시스템 분야에서는 차량의 궤적 데이터를 이용한 전자 도로 지도생성 시도가 많이 이루어져왔다. 이 목표를 이루기 위해서는 같은 도로 상의 궤적들을 모으는 방법이 필요하다. 흔히 프레셰 거리(Fréchet distance)가 궤적 쌍의 거리를 측정하는데 사용된다. 하지만 프레셰 거리는 대량의 궤적들에 대해서는 계산 시간의 소모가 심하다. 본 논문에서는 궤적들의 인접성 여부를 이산프레셰 거리를 통해 빠르게 구분하는 휴리스틱 알고리즘을 제안한다. 이 알고리즘은 계산되는 거리의 정확도를 낮추는 대신 계산 속도를 높였다. 실험 결과, 제안 방법은 이산 프레셰 거리 대비 95%의 정확도와최하 65%의 계산 감소율로 거리가 10m 이내인 궤적들을 구분할 수 있었다.

영어초록

A trajectory is the motion path of a moving object. The advances in IT have made it possible to collect an immeasurable amount of various type of trajectory data from a moving object using location detection devices like GPS. The trajectories of moving objects are widely used in many different fields of research, including the geographic information system (GIS) field. In the GIS field, several attempts have been made to automatically generate digital maps of roads by using the vehicle trajectory data. To achieve this goal, the method to cluster the trajectories on the same road is needed.
Usually, the Fréchet distance measure is used to calculate the distance between a pair of trajectories.
However, the Fréchet distance measure requires prolonged calculation time for a large amount of trajectories. In this paper, we presented a fast heuristic algorithm to distinguish whether the trajectories are in close distance or not using the discrete Fréchet distance measure. This algorithm trades the accuracy of the resulting distance with decreased calculation time. By experiments, we showed that the algorithm could distinguish between the trajectory within 10 meters and the distant trajectory with 95% accuracy and, at worst, 65% of calculation reduction, as compared with the discrete Fréchet distance.

참고자료

· 없음