With the widespread worldwide adoption of location-based service technologies, accurate and reliable driving trajectories have become crucial. However, because of the inherent deficiencies of sensor devices, accurate road matching results may not always be obtained directly from trajectory data, which poses a challenge for many location and trajectory based services. Existing map-matching techniques mainly focus on high-sampling-rate trajectory data while paying relatively less attention to low-frequency trajectory data. Low-sampling-rate trajectory data have greater matching difficulties than high-sampling-rate data owing to the limited available information. Moreover, in the case of signal loss or interference, the accuracy of map-matching algorithms can decrease significantly for low-sampling-rate data. To achieve accurate map-matching results for low-sampling-rate trajectory data, this study proposes a map-matching algorithm based on probability interpolation. First, the trajectory data are denoised to eliminate redundant trajectory points. Second, the concept of the probability truth value is introduced to handle the relationship between the interpolated virtual points and actual sampled trajectory points accurately. A higher probability truth value indicates a higher confidence level of the interpolation. Third, the denoised trajectory data are interpolated and a probability truth value is assigned based on the interpolation accuracy. Finally, a comprehensive probability composed of the probability truth value, emission probability, and transition probability is used to determine the correctly matched road segments. Experimental results on real trajectory datasets demonstrated that the proposed algorithm outperformed several advanced algorithms in terms of accuracy and performance.