Dynamically determining a tile budget when pre-fetching data in a client device

• US 8,886,715 B1
• Filed: 11/16/2011
• Issued: 11/11/2014
• 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 Gregory
• Primary Examiner(s): Wang, Liangche A
• Assistant Examiner(s): NDIAYE, CHEIKH T
• Application Number:
  US13/297,461
• Time in Patent Office: 1,091 Days
• Field of Search: 709/203, 709/217, 709/218, 709/219, 701/409, 701/410, 701/425, 701/426, 701/430
• US Class Current: 709/203
• CPC Class Codes: G06F 16/957 Browsing optimisation, e.g. caching or content distillation
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/5681 Pre-fetching or pre-delivering data based on network characteristics

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 that is dynamically adjusted in response to changing conditions on a 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 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;

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

requesting, from a remote map database storing the map data, the pre-fetch map data tiles corresponding to one or more map points of interest;

receiving, at the client device, the pre-fetch map data tiles from the remote map database;

during receiving of the pre-fetch map data tiles;

(i) determining a change in availability, at the client device, of memory or network bandwidth;

(ii) in response to determining the change in availability of memory or network bandwidth, dynamically adjusting, at the client device, the tile budget for storing the pre-fetch map data tiles at the client device; and

(iii) determining if the tile budget has been met by the received pre-fetch map data tiles, where;

when the tile budget has been met, the client device stops receiving additional pre-fetch map data tiles from the map database, and

when the tile budget has not been met, the client device continues receiving additional 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; 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 dynamically adjusting the tile budget comprises:

dynamically adjusting the tile budget based on an amount of map data memory available during receipt of the pre-fetch map data tiles and

setting the tile budget at or below the amount of map data memory available.

3. The method of claim 2, wherein the memory is a general memory for the client device.

4. The method of claim 2, wherein the memory is a map data specific memory for the client device.

5. The method of claim 2, wherein dynamically adjusting the tile budget further comprises:

updating a memory usage profile for the client device; and

adjusting the tile budget based on the updated memory usage profile.

6. The method of claim 1, wherein dynamically adjusting the tile budget comprises:

dynamically adjusting the tile budget based on an available number of map tile memory slots on the client device for storing the pre-fetch map data tiles.

7. The method of claim 6, the method further comprising:

determining an available amount of map data memory allocated for the client device to store the pre-fetch map data tiles;

accessing a memory allocation size for each map data tile; and

determining the number of map tile memory slots in the available amount of map data memory.

8. 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.

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

identifying a plurality of the map points of interest each corresponding to a portion of the pre-fetch map data tiles; and

prioritizing the plurality of the map points of interest in an order from highest to lowest, such that requesting the pre-fetch map data tiles comprises requesting the pre-fetch map data tiles in order from highest to lowest corresponding to plurality of map points of interest.

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 remote map database stores map data at different zoom levels, the map data at each zoom level containing a respective set of pre-fetch map data tiles.

12. The method of claim 11, wherein the map data at each zoom level contains pre-fetch map data tiles having a same memory allocation size.

13. The method of claim 1, the method further comprising awaiting a user interaction with the client device before identifying a subset of the pre-fetch map data tiles stored on the client device and rendering the visual display using the subset of the pre-fetch map data tiles.

14. 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 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;

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

request, from a remote map database storing the map data, the pre-fetch map data tiles corresponding to one or more map points of interest;

receive, at the client device, the pre-fetch map data tiles from the remote map database;

during receiving of the pre-fetch map data tiles;

(i) determine a change in availability, at the client device, of memory or network bandwidth;

(ii) in response to determining the change in availability of memory or network bandwidth, dynamically adjust the tile budget for storing the pre-fetch map data tiles at the client device;

(iii) determine, at the client device, if the tile budget has been met by the received pre-fetch map data tiles, where;

when the tile budget has been met, the client device stops receiving additional pre-fetch map data tiles from the map database, and

when the tile budget has not been met, the client device, continues receiving additional 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; and

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

15. The non-transitory computer-readable medium storing instructions of claim 14, wherein the instructions, when executed by a processor, cause the processor to dynamically adjust the tile budget based on an amount of map data memory available during receipt of the pre-fetch map data tiles, wherein dynamically adjusting the tile budget includes setting the tile budget at or below the amount of map data memory available.

16. The non-transitory computer-readable medium storing instructions of claim 15, wherein the memory is a general memory for the client device.

17. The non-transitory computer-readable medium storing instructions of claim 15, wherein the memory is a map data specific memory for the client device.

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

update a memory usage profile for the client device; and

adjust the tile budget based on the updated memory usage profile.

19. The non-transitory computer-readable medium storing instructions of claim 14, wherein the instructions, when executed by a processor, cause the processor to determine an available number of map tile memory slots on the client device for storing the pre-fetch map data tiles.

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

determine an available amount of map data memory allocated for the client device to store the pre-fetch map data tiles;

access a memory allocation size for each map data tile; and

determine the number of map tile memory slots in the available amount of map data memory.

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

receive, 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, determine, at the client device, if the tile budget has been met.

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

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

prioritize the plurality of the map points of interest in an order from highest to lowest, such that requesting the pre-fetch map data tiles comprises requesting the pre-fetch map data tiles in order from highest to lowest corresponding to plurality of map points of interest.

23. The non-transitory computer-readable medium storing instructions of claim 14, 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.

24. The non-transitory computer-readable medium storing instructions of claim 23, wherein the remote map database stores map data at different zoom levels, the map data at each zoom level containing a respective set of map data tiles.

25. The non-transitory computer-readable medium storing instructions of claim 23, wherein the map data at each zoom level contains pre-fetch map tiles having a same memory allocation size.

26. 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 of a computer system; and

one or more memories of the computer system 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 cause the computer system 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 cause the computer system 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 computer system for eventual rendering of a visual display of map data in response to a subsequent user request;

a database interface module including instructions executed on the one or more processors to cause the computer system to request, from the map database, the pre-fetch map data tiles from the remote map database and to receive 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, during receiving of the pre-fetch map data tiles, cause the computer system to;

(i) determine a change in availability, at the computer system, of memory or network bandwidth;

(ii) in response to determining the change in availability of memory or network bandwidth, dynamically adjust a previously determined tile budget for storing the pre-fetch map data tiles and determine if the tile budget has been met by the received pre-fetch map data tiles, wherein;

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

when the tile budget has not been met, the database interface module is to continue receiving additional 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.

27. The computer system of claim 26, wherein the tile budget module is to dynamically adjust the tile budget based on an amount of map data memory available during receipt of the pre-fetch map data tiles, wherein dynamically adjusting the tile budget comprises setting the tile budget at or below the amount of map data memory available.

28. The computer system of claim 27, wherein the memory is a general memory for the client device.

29. The computer system of claim 27, wherein the memory is a map data specific memory for the client device.

30. The computer system of claim 26, wherein the tile budget module includes further instructions executed on the one or more processors to:

update a memory usage profile for the client device; and

adjust the tile budget based on the updated memory usage profile.

33. The computer system of claim 26, 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.

34. The computer system of claim 26, wherein the plurality of modules, further include:

a zoom level module including 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 contains pre-fetch map data tiles having a same memory allocation size.

36. The computer system of claim 26, wherein the database interface module includes further instructions executed on the one or more processors to await a user interaction with the client device before identifying a subset of the pre-fetch map data tiles stored on the client device and to render the visual display using the subset of the pre-fetch map data tiles.

31. The computer system of 26, wherein the tile budget module includes further instructions executed on the one or more processors to determine an available number of map tile memory slots on the client device for storing the pre-fetch map data tiles.

32. The computer system of claim 31, wherein the tile budget module includes further instructions executed on the one or more processors to:

determine an available amount of map data memory allocated for the client device to store the pre-fetch map data tiles;

access a memory allocation size for each map data tile; and

determine the number of map tile memory slots in the available amount of map data memory.