Pre-fetching map data using variable map tile radius

• US 8,711,181 B1
• Filed: 11/16/2011
• Issued: 04/29/2014
• Est. Priority Date: 11/16/2011
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Nourse, Thomas Gregory, Siliski, Michael, CaveLie, Hans-Olav, Zhu, Ronghui
• Primary Examiner(s): Johnson, M Good
• Application Number:
  US13/297,720
• Time in Patent Office: 895 Days
• Field of Search: 345/660, 345/667
• US Class Current: 345/660
• CPC Class Codes: G01C 21/367 Details, e.g. road map scale, orientation, zooming, illumination, level of detail, scrolling of road map or positioning of current position marker
• CPC Class Codes: G01C 21/3811 Point data, e.g. Point of Interest [POI]
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 3/14 Digital output to display device ; Cooperation and interconnection of the display device with other functional units
• CPC Class Codes: G09G 2340/045 Zooming at least part of an image, i.e. enlarging it or shrinking it
• CPC Class Codes: G09G 2360/121 using a cache memory
• CPC Class Codes: G09G 2360/122 Tiling
• CPC Class Codes: H04W 4/185 by embedding added-value information into content, e.g. geo-tagging
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

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 and in the form of map data tiles. The system identifies those map data tiles that correspond to the subset of map data corresponding 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 pre-fetch map data tiles are identified using a variable map tile radius, which when extended from the points of interest defines the map tiles that qualify as pre-fetch map data tiles. The tile radius can be fixed or dynamically adjusted and changes across different map zoom levels.

Claims

1. A computer-implemented method comprising:

identifying, on a client device, a map point of interest;

identifying, from a plurality of zoom levels, one or more zoom levels for use in identifying map data for storage on the client device, where the map data is to be stored on the client device at different zoom levels, each zoom level containing a respective set of map data tiles;

identifying a different tile radius for each of the one or more determined zoom levels, where each tile radius corresponds to the map point of interest and defines, for each of the one or more zoom levels, pre-fetch map data tiles to be requested from a remote map database and stored on the client device for eventual rendering of the visual display in response to a subsequent user request;

requesting, from the remote map database, the pre-fetch map data tiles, wherein the map database stores map data in the form of a plurality of map data tiles, and the pre-fetch map data tiles are a sub-set of the plurality of map data tiles; and

receiving and storing the pre-fetch map data tiles in a local memory on the client device;

wherein the tile radius varies across different zoom levels in the map database and identifying a different tile radius for each of the one or more determined zoom levels comprises accessing tile radius data from a lookup table.

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

3. The method of claim 1, wherein identifying a different tile radius for each of the one or more determined zoom levels comprises adjusting the tile radius based on usage patterns of the user interacting with a previous visual display of the map data.

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

communicating the one or more determined zoom levels and the identified tile radius at each of the one or more determined zoom levels to a remote server connected to the client device through a communication network, where the remote map database is stored on the remote server;

the remote server accessing the remote map database to identify the pre-fetch map data tiles, in response to the communicated one or more zoom levels, the determined tile radius at each of the one or more zoom levels, and the map point of interest; and

the remote server communicating the identified pre-fetch map data tiles to the client device through the communication network.

5. The method of claim 1, wherein the number of zoom levels is n, wherein n is an integer greater than 1, and each zoom level contains a different amount of geographic detail.

6. The method of claim 1, wherein identifying the map point of interest comprises automatically determining the map point of interest based on a user'"'"'s usage data, a threshold analysis of a plurality of potential points of interest, most recently accessed points of interest, and/or most frequently accessed points of interest.

7. The method of claim 1, further comprising:

awaiting a user initiated request for a visual display of map data; and

rendering the visual display from a subset of the pre-fetch map data tiles stored in the local memory.

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

identify, on the client device, a map point of interest;

identify, from a plurality of zoom levels, one or more zoom levels for use in identifying map data for storage on the client device, where the map data is to be stored on the client device at different zoom levels, each zoom level containing a respective set of map data tiles;

identify a different tile radius for each of the one or more determined zoom levels, where each tile radius corresponds to the map point of interest and defines, for each of the one or more zoom levels, pre-fetch map data tiles to be requested from a remote map database and stored on the client device for eventual rendering of the visual display in response to a subsequent user request;

request, from the remote map database, the pre-fetch map data tiles, wherein the map database stores map data in the form of a plurality of map data tiles, and the pre-fetch map data tiles are a sub-set of the plurality of map data tiles;

receive and store the pre-fetch map data tiles in a local memory on the client device; and

access tile radius data from a lookup table.

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

10. The non-transitory computer-readable medium storing instructions of claim 8, wherein the tile radius varies across different zoom levels in the map database.

11. The non-transitory computer-readable medium storing instructions of claim 8, wherein the instructions, when executed by a processor, cause the processor to adjust the tile radius based on usage patterns of the user interacting with a previous visual display of the map data.

12. The non-transitory computer-readable medium storing instructions of claim 8, wherein the instructions, when executed by a processor, cause the processor to communicate the one or more determined zoom levels and the determined tile radius at each of the one or more determined zoom levels to a remote server connected to the client device through a communication network, where the remote map database is stored on the remote server.

13. The non-transitory computer-readable medium storing instructions of claim 8, wherein the instructions, when executed by a processor, cause the processor to automatically determine the map point of interest based on a user'"'"'s usage data, a threshold analysis of a plurality of potential points of interest, most recently accessed points of interest, and/or most frequently accessed points of interest.

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

await a user initiated request for a visual display of map data; and

render the visual display from a subset of the pre-fetch map data tiles stored in the local memory.

15. 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:

a map point identifier module that identifies a map point of interest;

a zoom level module that identifies one or more zoom levels for use in identifying map data for storage on the client device, where the map data is to be stored on the client device at different zoom levels, each zoom level containing a respective set of map data tiles;

a map tile radius module that determines a different tile radius for each of the one or more determined zoom levels, where each tile radius corresponds to the map point of interest and defines, for each of the one or more zoom levels, pre-fetch map data tiles to be requested from a remote map database and stored on the client device for eventual rendering of the visual display in response to a subsequent user request; and

a database interface module to receive, from the map database, the pre-fetch map data tiles corresponding to the map point of interest and to store the pre-fetch map data tiles in a local memory on the client device;

wherein the map tile radius module determines the tile radius associated with each zoom level by accessing tile radius data from a lookup table.

16. The computer system of claim 15, where the map data at each zoom level is stored in map tiles having the same memory allocation size.

17. The computer system of claim 15, where the tile radius varies across different zoom levels in the map database.

18. The computer system of claim 15, wherein the map tile radius module determines the tile radius associated with the map point of interest by adjusting the tile radius based on usage patterns of a user interacting with a previous visual display of the map data.

19. The computer system of claim 15, wherein the database interface module communicates the map point of interest, the one or more determined zoom levels, and the tile radius at each of the one or more determined zoom levels to a remote server connected to the client device through a communication network, where the remote map database is stored on the remote server.

20. The computer system of claim 15, wherein the map point identifier module automatically determines the map point of interest based on a user'"'"'s usage data, a threshold analysis of a plurality of potential points of interest, most recently accessed points of interest, and/or most frequently accessed points of interest.

21. The computer system of claim 15, wherein the map tile radius increases with zoom level.

22. The computer system of claim 15, wherein the map tile radius is the same for at least two zoom levels.