This paper presents a systematic solution to efficiently estimate the traffic state of large-scale urban road networks. We first propose the new approach to construct the exact GIS-T digital map. The exact digital map can lay the solid foundation for the traffic state estimation with the data from Global Positioning System (GPS) probe vehicles. Then, we present the following two effective methods based on GPS probe vehicles for the traffic state estimation: 1) the curve-fitting-based method and 2) the vehicle-tracking-based method. Finally, we test the proposed solution with a large number of real data from GPS probe vehicles and the standard digital map of Shanghai, China. In the experiments, data from thousands of GPS-equipped taxies were taken as the probe vehicles. The estimation accuracy and operation speed of the two different methods were systematically measured and compared. In addition, the coverages of the GPS sampling points were also investigated for the large-scale urban road network in the spatial and temporal domains. For the accuracy experiment, the ground truth was obtained by repeating the videos that were recorded on 24 road sections in downtown Shanghai. The experimental results illustrate that the proposed methods are effective and efficient in monitoring the traffic state of large-scale urban road networks. © 2000-2011 IEEE.