A method for navigation includes storing map data on a server, the map data including vector information delineating roads in a map. A portion of the vector information corresponding to an area in which a user of a mobile client device is traveling is downloaded from the server to the client device. Approximate position coordinates of the user are found using a location providing device associated with the client device and are corrected in the client device, using the downloaded vector information, so as to determine a location of the user on one of the roads in the map. A navigation aid is provided to the user of the client device based on the determined location.