Abstract: A double-clustering method is proposed for GPS trajectories in urban networks that efficiently identify trajectories with similar spatio-temporal and speed properties. The Spatio-temporal ranges of congested urban road segments are identified based on the trajectory velocity threshold. This paper defines similar queues and designs a DBSCAN based clustering method. By merging similar sub-trajectories into similar queues, the proposed method reduces computation costs. An improved trajectory similarity measure is used to calculate the spatio-temporal distance between similar queues. A C-means clustering method is applied. An experiment is implemented by clustering the floating car trajectories in Guangzhou, China; the results show that the proposed method can not only reflect the change of traffic congestion in space and time, but also improves computational efficiency when dealing with large-scale trajectory data.