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

• US 9,307,045 B2
• Filed: 11/10/2014
• Issued: 04/05/2016
• 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): NDIAYE, CHEIKH T
• Application Number:
  US14/537,537
• Publication Number:
  US 20150067040A1
• Time in Patent Office: 512 Days
• Field of Search: 709/203, 709/217, 709/218, 709/219
• US Class Current: 1/1
• 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:

receiving an indication, at remote map database from a client device, of one or more map points of interest;

identifying, based on the received indication, pre-fetch map data;

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

receiving a request for the pre-fetch map data corresponding to one or more map points of interest;

determining a change in availability of client device memory or network bandwidth;

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

determining if the request for the pre-fetch map data meets the budget;

when the budget has not been met, sending pre-fetch map data until the budget is met or until all pre-fetch map data 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 in a local memory on the client device until a subsequent user request.

2. The computer-implemented method of claim 1, wherein dynamically adjusting the budget comprises:

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

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

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

5. The computer-implemented of claim 2, wherein dynamically adjusting the budget further comprises:

updating a memory usage profile for the client device; and

adjusting the budget based on the updated memory usage profile.

6. The computer-implemented of claim 1, wherein dynamically adjusting the budget comprises:

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

7. The computer-implemented 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;

accessing a memory allocation size for the pre-fetch map data; and

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

8. The computer-implemented of claim 1, the method comprising:

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

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

9. The computer-implemented 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; 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 comprises requesting the pre-fetch map data in order from highest to lowest corresponding to plurality of map points of interest.

10. The computer-implemented of claim 1, further comprising:

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

11. The computer-implemented of claim 10, further comprising storing the pre-fetch map data at different zoom levels, the pre-fetch map data at each zoom level containing a respective set of pre-fetch map data tiles.

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

13. The computer-implemented 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 stored on the client device and rendering the visual display using the subset of the pre-fetch map data.

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

receive an indication, at a remote database from a client device, of one or more map points of interest;

identify, based on the received indication, pre-fetch map data;

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

receive a request for the pre-fetch map data corresponding to one or more map points of interest;

determine a change in availability of client device memory or network bandwidth;

in response to determining the change in availability of memory or network bandwidth, dynamically adjust the budget for storing the pre-fetch map data at the client device during receipt of the pre-fetch map data at the client device; and

determine if the request for the pre-fetch map data meets the budget;

when the budget has not been met, send pre-fetch map data to the client device until the budget is met or until all pre-fetch map data 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 in a local memory on the client device until a subsequent user request.

15. The non-transitory computer-readable memory of claim 14, wherein the instruction to dynamically adjust the budget for storing the pre-fetch map data at the client device comprises an instruction to set the budget at or below an amount of map data memory available, wherein the map data memory is either a general memory for the client device or a map data specific memory for the client device.

16. The non-transitory computer-readable memory of claim 15, wherein the instruction to dynamically adjust the budget based on an amount of map data memory available during receipt of the pre-fetch map data further comprises instructions to:

update a memory usage profile for the client device; and

adjust the budget based on the updated memory usage profile.

17. The non-transitory computer-readable memory of claim 15, wherein the instruction to dynamically adjust the budget based on an amount of map data memory available during receipt of the pre-fetch map data further comprises instructions to:

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

access a memory allocation size for the map data; and

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

18. A computer system for fetching map 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;

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 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 from the remote map database and to receive the pre-fetch map data from the remote map database; and

a budget module including instructions executed on the one or more processors to cause the computer system to;

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

in response to determining the change in availability of memory or network bandwidth, dynamically adjust a budget for storing the pre-fetch map data and determine if the budget has been met by the received pre-fetch map data during receipt of the pre-fetch map data at the client device; and

when the budget has not been met, the map data interface module receives additional pre-fetch map data until the budget is met or until all pre-fetch map data corresponding to the one or more map points of interest have been received at the client device.

19. The computer system of claim 18, wherein the instruction to dynamically adjust the budget for storing the pre-fetch map data further includes instructions to:

update a memory usage profile for the client device; and

adjust the budget based on the updated memory usage profile.

20. The computer system of claim 18, wherein the instruction to dynamically adjust the budget for storing the pre-fetch map data further includes instructions to:

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

access a memory allocation size for the map data; and

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