This paper presents development and application of a real-time virtual differential map-matching approach which makes use of the slow drifting property of the GPS errors and the continuous and gradual evolving characteristic of map errors to improve the accuracy and computational efficiency. A differential vector is created to approximate the real-time deviation, which is corrected continuously along with the vehicle movement during the map-matching process. Real-life application of the algorithm to the City of Hefei, a metropolis of China, shows that it corrects both GPS errors and digital map errors reasonably well with improved computational efficiency.