Pre-fetching map data based on a tile budget

• US 9,063,951 B1
• Filed: 11/16/2011
• Issued: 06/23/2015
• Est. Priority Date: 11/16/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zhu, Ronghui, Nourse, Thomas G.
• Primary Examiner(s): Wang, Liangche A
• Assistant Examiner(s): Ndiaye, Cheikh
• Application Number:
  US13/297,382
• Publication Number:
  US 20150186413A1
• Time in Patent Office: 1,315 Days
• Field of Search: 709/203, 701/409, 701/410, 701/425, 701/426, 701/430, 701/450, 701/451, 701/452, 701/453
• US Class Current: 1/1
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: G06T 3/40 Scaling of whole images or parts thereof, e.g. expanding or contracting
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A pre-fetching map data system and method identifies a subset of map data to corresponding to one or more points of interest to be displayed on the map. The map data is stored on a remote map database in map data tiles. The pre-fetching map data system identifies those map data tiles that correspond to the one or more points of interest, where the identified pre-fetch map data tiles are sent from the remote database to a client device for cache storage. The number of pre-fetch map data tiles are determined using a tile budget, such as a maximum number of map data tiles that may be stored on the client device or a maximum amount of map data memory that can be consumed on the client device.

Claims

1. A computer-implemented method comprising:

identifying, on a client device, one or more map points of interest;

identifying, based on the map points of interest, pre-fetch map data tiles to be requested from a hardware server communicatively coupled to a remote map database and stored on the client device for eventual rendering of a visual display of map data in response to a subsequent user request, wherein each pre-fetch map data tile includes vector data for the client device to construct a portion of a map for display at a single zoom level;

determining, at the client device, a tile budget for storing the pre-fetch map data tiles at the client device;

prioritizing, at the client device, a plurality of the map points of interest in an order from highest to lowest based on prior access of the plurality of the map points of interest by the client device;

requesting, from the hardware server communicatively coupled to the remote map database storing the map data, the pre-fetch map data tiles corresponding to the plurality of the map points of interest in order from highest to lowest priority corresponding to one or more map points of interest;

receiving, at the client device, a subset of the pre-fetch map data tiles from the hardware server communicatively coupled to the remote map database in order from highest to lowest priority; and

,

during receiving of the pre-fetch map data tiles at the client device, determining, at the client device, if the tile budget has been met by the received pre-fetch map data tiles, where,

if the tile budget has been met by the received subset of the pre-fetch map data tiles, the client device stops receiving additional pre-fetch map data tiles from the map database, and

if the tile budget has not been met, the client device sends a signal to the hardware server communicatively coupled to the remote map database to send a next subset of the pre-fetch map data tiles;

wherein the subset of the pre-fetch map data tiles includes a higher priority than the next subset of the pre-fetch map data tiles and the client device continues receiving additional, prioritized subsets of the pre-fetch map data tiles from the hardware server communicatively coupled to the remote map database until the tile budget is met or until all pre-fetch map data tiles corresponding to the one or more map points of interest have been received at the client device; and

storing the received pre-fetch map data tiles in a local memory on the client device until a subsequent user request.

2. The method of claim 1, wherein the tile budget is a preset total number of map data tiles that are to be received at the client device.

3. The method of claim 1, wherein the tile budget is a preset total amount of map data that is to be received at the client device.

4. The method of claim 1, the method comprising:

receiving, at the client device, the pre-fetch map data tiles in a sequential manner; and

in response to receiving each pre-fetch map data tile, determining, at the client device, if the tile budget has been met.

5. The method of claim 4, wherein prioritizing, at the client device,

the plurality of map points of interest based on user usage data.

6. The method of claim 5, wherein prioritizing, at the client device, the plurality of the map points of interest in an order from highest to lowest based on prior access of the plurality of the map points of interest by the client device further includes prioritizing the plurality of map points of interest based on which map points of interest were most recently accessed.

7. The method of claim 5, wherein prioritizing, at the client device, the plurality of the map points of interest in an order from highest to lowest based on prior access of the plurality of the map points of interest by the client device further includes prioritizing the plurality of map points of interest based on which map points of interest were most frequently accessed.

8. The method of claim 1, wherein prioritizing, at the client device, the plurality of the map points of interest in an order from highest to lowest based on prior access of the plurality of the map points of interest by the client device further includes prioritizing the plurality of map points of interest based on an amount of time a map point of interest was displayed on a previously rendered visual display of map data.

9. The method of claim 1, wherein prioritizing, at the client device, the plurality of the map points of interest in an order from highest to lowest based on prior access of the plurality of the map points of interest by the client device further includes prioritizing the plurality of map points of interest based on a previous user selection.

10. The method of claim 1, further comprising

identifying, from a plurality of zoom levels, one or more zoom levels, such that the pre-fetch map data tiles are identified based on the one or more map points of interest and the identified one or more zoom levels.

11. The method of claim 10, wherein the map data at each zoom level is stored in map data tiles having a same memory allocation size.

12. A non-transitory computer-readable medium storing instructions, the instructions when executed by a processor cause the processor to:

identify, on a client device, one or more map points of interest;

identify, based on the map points of interest, pre-fetch map data tiles to be requested from a hardware server communicatively coupled to a remote map database and stored on the client device for eventual rendering of a visual display of map data in response to a subsequent user request, wherein each pre-fetch map data tile includes vector data for the client device to construct a portion of a map for display at a single zoom level;

determine, at the client device, a tile budget for storing the pre-fetch map data tiles at the client device;

prioritize, at the client device, a plurality of the map points of interest in an order from highest to lowest based on prior access of the plurality of the map points of interest by the client device;

request, from the hardware server communicatively coupled to the remote map database storing the map data, the pre-fetch map data tiles in order from highest to lowest priority corresponding to one or more map points of interest;

receive, at the client device, a subset of the pre-fetch map data tiles from the hardware server communicatively coupled to the remote map database; and

,

during receiving of the subset of the pre-fetch map data tiles at the client device, determining, at the client device, if the tile budget has been met by the received subset of the pre-fetch map data tiles, where,

if the tile budget has been met by the received subset of the pre-fetch map data tiles, the client device stops receiving additional pre-fetch map data tiles from the map database, and

if the tile budget has not been met, the client device sends a signal to the hardware server communicatively coupled to the remote map database to send a next subset of the pre-fetch map data tiles;

wherein the subset of the pre-fetch map data tiles includes a higher priority than the next subset of the of the pre-fetch map data tiles and the client device continues receiving additional, prioritized subsets of the pre-fetch map data tiles from the hardware server communicatively coupled to the remote map database until the tile budget is met or until all pre-fetch map data tiles corresponding to the one or more map points of interest have been received at the client device; and

store the received pre-fetch map data tiles in a local memory on the client device until a subsequent user request.

13. The non-transitory computer-readable medium storing instructions of claim 12, wherein the tile budget is a preset total number of map data tiles that are to be received at the client device.

14. The non-transitory computer-readable medium storing instructions of claim 12, wherein the tile budget is a preset total amount of map data that is to be received at the client device.

15. The non-transitory computer-readable medium storing instructions of claim 12, wherein the instructions, when executed by a processor, cause the processor to:

receive, at the client device, pre-fetch map data tiles in a sequential manner; and

in response to receiving each pre-fetch map data tile, determine, at the client device, if the tile budget has been met.

16. The non-transitory computer-readable medium storing instructions claim 15, wherein the instructions to prioritize, at the client device, the plurality of the map points of interest in an order from highest to lowest, when executed by a processor, further cause the processor to prioritize the plurality of map points of interest based on user usage data.

17. The non-transitory computer-readable medium storing instructions of claim 16, wherein the instructions to prioritize, at the client device, the plurality of the map points of interest in an order from highest to lowest based on prior access of the plurality of the map points of interest by the client device, when executed by a processor, further cause the processor to prioritize the plurality of map points of interest based on which map points of interest were most recently accessed.

18. The non-transitory computer-readable medium storing instructions of claim 16, wherein the instructions to prioritize, at the client device, the plurality of the map points of interest in an order from highest to lowest based on prior access of the plurality of the map points of interest by the client device, when executed by a processor, further cause the processor to prioritize the plurality of map points of interest based on which map points of interest were most frequently accessed.

19. The non-transitory computer-readable medium storing instructions of claim 12, wherein the instructions to prioritize, at the client device, the plurality of the map points of interest in an order from highest to lowest based on prior access of the plurality of the map points of interest by the client device, when executed by a processor, further cause the processor to prioritize the plurality of map points of interest based on an amount of time a map point of interest is displayed on a previously rendered visual display of map data.

20. The non-transitory computer-readable medium storing instructions of claim 12, wherein the instructions to prioritize, at the client device, the plurality of the map points of interest in an order from highest to lowest based on prior access of the plurality of the map points of interest by the client device, when executed by a processor, further cause the processor to prioritize the plurality of map points of interest based on previous user selection.

21. The non-transitory computer-readable medium storing instructions of claim 12, wherein the instructions, when executed by a processor, cause the processor to identify, from a plurality of zoom levels, one or more zoom levels, such that the pre-fetch map data tiles are identified based on the one or more map points of interest and the identified one or more zoom levels.

22. The non-transitory computer-readable medium storing instructions of claim 21, wherein the map data at each zoom level is stored in map data tiles having a same memory allocation size.

23. A computer system for fetching map tile data to be used in constructing a visual display of map data on a client device, the computer system comprising:

one or more processors; and

one or more memories storing a plurality of modules including instructions for execution on the one or more processors, the modules including

a display module including instructions executed on the one or more processors to construct and display the visual display of the map data, where the map data is stored in a remote map database as a plurality of map data tiles;

a map point identifier module including instructions executed on the one or more processors to prioritize, at the client device, the plurality of the map points of interest in an order from highest to lowest, to identify one or more map points of interest that define pre-fetch map data tiles that are requested from a remote map database and stored on the client device for eventual rendering of a visual display of map data in response to a subsequent user request, wherein each pre-fetch map data tile includes vector data for the client device to construct a portion of a map for display at a single zoom level;

a database interface module including instructions executed on the one or more processors to request, from the map database, the pre-fetch map data tiles in order from highest to lowest priority from the remote map database and to receive a subset of the pre-fetch map data tiles from the remote map database; and

a tile budget module including instructions executed on the one or more processors to determine, at the client device, a tile budget for storing the pre-fetch map data tiles at the client device, and during receiving of the subset of the pre-fetch map data tiles, to determine if tile budget has been met by the received subset of the pre-fetch map data tiles, where,

if the tile budget has been met by the received subset of the pre-fetch map data tiles, the database interface module is to stop receiving additional pre-fetch map data tiles from the remote map database, and

if the tile budget has not been met, the database interface module sends a signal to the hardware server communicatively coupled to the remote map database to send a next subset of the pre-fetch map data tiles;

wherein the subset of the pre-fetch map data tiles includes a higher priority than the next subset of the of the pre-fetch map data tiles and the client device is to continue receiving additional, prioritized subsets of the pre-fetch map data tiles from the map database until the tile budget is met or until all pre-fetch map data tiles corresponding to the one or more map points of interest have been received at the client device.

24. The computer system of claim 23, wherein the tile budget is a preset total number of map data tiles that are to be received at the client device.

25. The computer system of claim 23, wherein the tile budget is a preset total amount of map data that is to be received at the client device.

26. The computer system of claim 23, wherein the tile budget module includes further instructions executed on the one or more processors to determine if the tile budget has been met upon receipt of each pre-fetch map data tile.

27. The computer system of claim 23, wherein the map point identifier module includes further instructions executed on the one or more processors to:

identify a plurality of the map points of interest each corresponding to a portion of the pre-fetch map data tiles.

28. The computer system of claim 27, wherein the database interface module includes further instructions executed on the one or more processors to request the pre-fetch map data tiles for each of the plurality of map points of interest in order from highest to lowest, until the tile budget module determines that the tile budget has been reached.

29. The computer system of claim 27, wherein the map point identifier module further prioritizes the plurality of map points of interest based on user usage data.

30. The computer system of claim 27, wherein the map point identifier module further prioritizes the plurality of map points of interest based on which map points of interest were most recently accessed.

31. The computer system of claim 27, wherein the map point identifier module further prioritizes the plurality of map points of interest based on which map points of interest were most frequently accessed.

32. The computer system of claim 27, wherein the map point identifier module further prioritizes the plurality of map points of interest based on an amount of time a map point of interest is displayed on a previous visual display of map data.

33. The computer system of claim 27, wherein the map point identifier module further prioritizes the plurality of map points of interest based on user selection.

34. The computer system of claim 27, further comprising:

a zoom level module that includes further instructions executed on the one or more processors to identify, from a plurality of zoom levels, one or more zoom levels, such that the pre-fetch map data tiles are defined based on the one or more map points of interest and the identified one or more zoom levels, and wherein the remote map database stores map data at different zoom levels, each zoom level containing a respective set of map data tiles.

35. The computer system of claim 34,

wherein the map data at each zoom level is stored in map data tiles having a same memory allocation size.