In one embodiment, a method includes receiving a sequence of location points and motion data associated with a mobile computing device. The method further includes generating, based on the motion data, a motion-data trace of a path and calculating, for each location point, a distance between the location point and a point on the motion-data trace of the path. The method further includes determining that the distance associated with at least one location point exceeds a threshold distance. The method further includes generating an estimated path traveled by the mobile computing device using (1) the point on the motion-data trace of the path used for calculating the distance associated with each of the at least one location point and (2) the received location point for each of the sequence of location points whose associated distance is at or within the threshold distance.