1. A method of adding a new landmark to a map for navigation of a mobile device, the method comprising: navigating the mobile device using the map, and while navigating the mobile device, performing the following: retrieving dead reckoning data from at least a time corresponding to a prior update of device pose of the mobile device and a time corresponding to an observation of the new landmark; retrieving a prior device pose of the mobile device for the map, wherein the prior device pose of the mobile device corresponds to a prior update time; and adding the new landmark to the map, wherein the pose associated with the new landmark is computed at least in part by using the retrieved dead reckoning data to calculate a change to device pose of the mobile device corresponding to the prior update, wherein the new landmark is used for navigation of the same mobile device; wherein navigating, retrieving and adding are performed under the control of electronic hardware.