We present the design and implementation of ParkMaster, a system that leverages the ubiquitous smartphone to help drivers find parking spaces in the urban environment. ParkMaster estimates parking space availability using video gleaned from drivers' dash-mounted smartphones on the network's edge, uploading analytics about the street to the cloud in real time as participants drive. Novel lightweight parked-car localization algorithms enable the system to estimate each parked car's approximate location by fusing information from phone's camera, GPS, and inertial sensors, tracking and counting parked cars as they move through the driving car's camera frame of view. To visually calibrate the system, ParkMaster relies only on the size of well-known objects in the urban environment for on-The-go calibration. We implement and deploy ParkMaster on Android smartphones, uploading parking analytics to the Azure cloud. On-The-road experiments in three different environments comprising Los Angeles, Paris and an Italian village measure the end-To-end accuracy of the system's parking estimates (close to 90%) as well as the amount of cellular data usage the system requires (less than one megabyte per hour). Drill-down microbenchmarks then analyze the factors contributing to this end-To-end performance, as video resolution, vision algorithm parameters, and CPU resources.