A system and method for estimating street parking availability for a user is disclosed. The system comprises a communication module and a parking probability generator. The communication module receives data describing a set of traces for a group of vehicles associated with a group of users. The parking probability generator assigns the set of traces to one or more street segments based at least in part on street segment data describing the one or more street segments. The parking probability generator generates one or more parking probabilities for the one or more street segments based at least in part on one or more user densities in the one or more street segments.