Abstract We study the problem of map-matching, or finding the route on a road network from a trace of noisy and sparse observed points, particularly when a huge number of points are given. The algorithms based on Hidden Markov Models (HMMs) are known to achieve high accuracy for noisy and sparse data but suffer from high computational cost. We find that the bottleneck of the HMM-based map-matching is in the shortest path search for calculating transition probabilities. We propose a technique to truncate the shortest path search before finding all the shortest paths in the HMM-based map-matching without losing accuracy. We run the one-to-many shortest path search on the reversed network and terminate the search based on the log likelihood of the Viterbi algorithm. Computational experiments show that the proposed approaches can reduce the computational cost by a factor of at least 5.4.