The development of auto society has brought a series of problems such as air pollution, traffic jams, etc. Car-sharing viewed as a green travel way is encouraged by the government and now known and accepted by more and more people. In the past one year, the carpool market has grown up at a high speed. The development of carpool needs an efficient information exchange platform, and a carpool matching system based on similar trajectory is the most important part. This paper mainly focused on developing an efficient method to solve the similar trajectory matching problem. With a full study of related research, we proposed a method consists of two steps: first step divide the trajectories into small groups based on clustering technique and then find the matching pair within each group. First of all, we described the carpool matching problem, then give the trajectory model that will be used in this paper. Then we discussed different type of matching trajectories. All related methods are also introduced in this chapter, then we proposed our algorithm. Then proposed a new acceleration method based on the thought of dynamical and immediate adjustment of the center K-means with triangle inequality. The triangle inequality is used to avoid redundant distance computations; But unlike Elkan's algorithm, the centers are divided into outer-centers and inner-centers for each data point in the first place, and only the tracks of the lower bounds to inner-centers are kept; On the other hand, by adjusting the data points cluster by cluster and updating the cluster center immediately right after finishing each cluster’s adjustment, the number of iteration is effectively reduced. The experiment results show that our algorithm runs much faster than Elkan's algorithm with much less memory consumption when the cluster center number is larger than 20 and the dataset records number is greater than 10 million, and the speedup becomes better when the k increases. To better deal with the trajectory, we also proposed a time-weighted-netword build algorithm based on key trajectory points clustering.