@article{M4B47BF35,
title = "An Efficient Clustering Algorithm for Massive GPS Trajectory Data",
journal = "Journal of KIISE, JOK",
year = "2016",
issn = "2383-630X",
doi = "",
author = "Taeyong Kim,Bokuk Park,Jinkwan Park,Hwan-Gue Cho",
keywords = "trajectory clustering,GPS data,road map generation,line sweeping",
abstract = "Digital road map generation is primarily based on artificial satellite photographing or in-site manual survey work. Therefore, these map generation procedures require a lot of time and a large budget to create and update road maps. Consequently, people have tried to develop automated map generation systems using GPS trajectory data sets obtained by public vehicles. A fundamental problem in this road generation procedure involves the extraction of representative trajectory such as main roads. Extracting a representative trajectory requires the base data set of piecewise line segments(GPS-trajectories), which have close starting and ending points. So, geometrically similar trajectories are selected for clustering before extracting one representative trajectory from among them. This paper proposes a new divide- and-conquer approach by partitioning the whole map region into regular grid sub-spaces. We then try to find similar trajectories by sweeping. Also, we applied the Fréchet distance measure to compute the similarity between a pair of trajectories. We conducted experiments using a set of real GPS data with more than 500 vehicle trajectories obtained from Gangnam-gu, Seoul. The experiment shows that our grid partitioning approach is fast and stable and can be used in real applications for vehicle trajectory clustering."
}