Techniques for displaying and caching tiled map data on constrained-resource services

• US 20070080830A1
• Filed: 08/11/2005
• Published: 04/12/2007
• Est. Priority Date: 08/11/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Sacks, Josh
• Granted Patent: US 7,315,259 B2
• Time in Patent Office: Days
• US Class Current: 340/995.100
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G06F 3/147 using display panels
• CPC Class Codes: G09G 2340/145 related to small screens
• CPC Class Codes: G09G 2360/122 Tiling

Abstract

Techniques are disclosed that enable users to access and use digital mapping systems with constrained-resource services and/or mobile devices (e.g., cell phones and PDAs). In particular, latency of a mapping application on high-latency and low-throughput networks is minimized. One embodiment utilizes volatile and non-volatile storage of the mobile device to cache pre-computed map images (e.g., map tiles). An asynchronous cache can be used to prevent delays caused by potentially slow non-volatile storage. Meta-data about each map image and usage patterns can be stored and used by the cache to optimize hit rates.

Claims

1. A method for providing a tile-based map on a mobile device that is communicatively coupled to a tile-based mapping system, the method comprising:

determining which map tiles of the tile-based mapping system are required to draw a requested map;

in response to a required map tile being stored in a heap cache of the mobile device, drawing that map tile for display on the mobile device;

in response to a required map tile being stored in a flash cache of the mobile device, loading that map tile into the heap cache; and

in response to a required map tile not being stored in the flash cache or the heap cache, queuing the tile for download from a remote tile server of the tile-based mapping system.

2. The method of claim 1 wherein the mobile device is a cell phone or a personal digital assistant or a combination of the two.

3. The method of claim 1 wherein in response to a required map tile being stored in a flash cache of the mobile device, the method further includes drawing the map tile for display on the mobile device after it is loaded into the heap cache.

4. The method of claim 1 wherein in response to a required map tile not being stored in the flash cache or the heap cache, the method further includes generating a placeholder tile image for tile queue for download.

5. The method of claim 1 wherein in response to a required map tile not being stored in the flash cache or the heap cache, the method further includes drawing the map tile for display on the mobile device after it is downloaded.

6. The method of claim 1 wherein queued map tiles are requested for download asynchronously once all missing tiles have been identified.

7. The method of claim 1 wherein at least one missing tile is not downloaded based on heuristics indicating there is a high likelihood that need for the at least one missing tile is fleeting.

8. The method of claim 1 wherein missing map tiles are downloaded in a background thread that operates contemporaneously with accessing of the caches.

9. The method of claim 1 wherein while missing tiles are downloading, a temporary map tile image is displayed for at least one of the missing tiles.

10. The method of claim 9 wherein the temporary image is a low-resolution map image derived from a lower-level zoom.

11. The method of claim 1 wherein the flash cache is maintained by an asynchronous process that carries out both insertion and removal of map tiles from the flash cache, including:

sorting map tiles in the heap cache based on respective scores;

selecting a new block of N top score map tiles for writing to the flash cache; and

in response to there being room in the flash cache for the new block, adding map tiles of the new block to the flash cache.

12. The method of claim 11 wherein in response to there being insufficient room in the flash cache for the new block, the method further comprising:

identifying a lowest score block in the flash cache; and

in response to the score of the identified block being worse than a score of the new block, replacing the identified block with the new block in the flash cache.

13. The method of claim 12 wherein in response to the score of the identified block not being worse than the score of the new block, maintaining the flash cache as is.

14. The method of claim 1 wherein the heap cache is maintained by an asynchronous process, comprising:

detecting that the heap cache exceeds its maximum size;

sorting the map tiles in the heap cache based on respective scores; and

removing lowest score map tiles from the heap cache, until its size is under the maximum size.

15. The method of claim 1 further comprising:

calculating a score for each map tile stored in the caches based last access time of tile.

16. The method of claim 1 further comprising:

calculating a score for each map tile stored in the caches based on at least one of tile zoom level and user access pattern of tile.

17. The method of claim 1 wherein each map tile is about 64 pixels per side.

18. A method for providing a tile-based map on a mobile device including at least one of a cell phone and a personal digital assistant, that is communicatively coupled to a tile-based mapping system, the method comprising:

determining which map tiles of the tile-based mapping system are required to draw a requested map, each map tile having a size of about 64 pixels per side;

in response to a required map tile being stored in a heap cache of the mobile device, drawing that map tile for display on the mobile device;

in response to a required map tile being stored in a flash cache of the mobile device, loading that map tile into the heap cache and then drawing the map tile for display on the mobile device; and

in response to a required map tile not being stored in the flash cache or the heap cache, at least one of queuing the tile for download from a remote tile server of the tile-based mapping system, generating a placeholder tile image for tile queue for download, and drawing the map tile for display on the mobile device after it is downloaded.

19. The method of claim 18 wherein at least one missing tile is not downloaded based on heuristics indicating there is a high likelihood that need for the at least one missing tile is fleeting.

20. The method of claim 18 further comprising:

calculating a score for each map tile stored in the caches based on at least one of last access time of tile, tile zoom level, and user access pattern of tile; and

maintaining the caches based on the scores.

21. A method for providing a tile-based map on a mobile device that is communicatively coupled to a tile-based mapping system, the method comprising:

determining which map tiles of the tile-based mapping system are required to draw a requested map, each map tile having a size that reduces required data bytes per screen as compared to other map tile sizes;

in response to a required map tile being stored in a volatile cache of the mobile device, drawing that map tile for display on the mobile device;

in response to a required map tile being stored in a non-volatile cache of the mobile device, loading that map tile into the volatile cache; and

in response to a required map tile not being stored in the mobile device, requesting the tile for download from the tile-based mapping system.

22. The method of claim 21 wherein the mobile device is a cell phone or a personal digital assistant or a combination of the two.

23. The method of claim 21 wherein at least one missing tile is not downloaded based on heuristics indicating there is a high likelihood that need for the at least one missing tile is fleeting.

24. The method of claim 21 wherein while missing tiles are downloading, a temporary map tile image is displayed for at least one of the missing tiles.

25. The method of claim 21 further comprising:

calculating a score for each map tile stored in the mobile device based on at least one of last access time of tile, tile zoom level, and user access pattern of tile; and

maintaining stored map tiles based on the scores.

26. The method of claim 21 wherein each map tile is about 32 to 128 pixels per side.