Background. Real time urban traffic information is critical to wide populations living in the city but undergoes significant spatial and temporal variation especially in the urban areas and calls for well monitoring. For the past decades, increasing efforts have been put into exploring an accurate, efficient, and inexpensive way to instantly monitor the urban traffic conditions. Conventional methods rely on intrusive sensing, where people deploy infrastructural devices like loop detectors or traffic cameras at roadsides to actively detect traffic references. Installing such intrusive devices incurs substantial deployment and maintenance costs and can only provide limited observation at sparse positions. Recent studies resort to the GPS traces collected from "probe vehicles" like taxis or private cars to estimate the road traffic conditions [2, 5]. Such a passive probing method avoids cumbrous infrastructure deployment and enjoys flexible information extraction from the running probes in the city. Nevertheless, most of them largely rely on full cooperation from the probe vehicles and bear substantial cost in obtaining their location references.