Pre-fetching map tile data along a route

• US 8,803,920 B2
• Filed: 07/11/2012
• Issued: 08/12/2014
• Est. Priority Date: 12/12/2011
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kalai, Iljya, Siliski, Michael, Morrison, Jerry, Ito, Keith, Miller, Andrew T.
• Primary Examiner(s): Tung, Kee M
• Assistant Examiner(s): CHEN, FRANK S
• Application Number:
  US13/546,143
• Publication Number:
  US 20130147846A1
• Time in Patent Office: 762 Days
• US Class Current: 345/660
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• 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/3881 Tile-based structures
• CPC Class Codes: G01C 21/3889 Transmission of selected map data, e.g. depending on route
• CPC Class Codes: G01C 21/3896 Transmission of map data from central databases
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 3/147 using display panels
• CPC Class Codes: G06T 1/60 Memory management
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06T 17/05 Geographic models

Abstract

The present application describes techniques for fetching map data as a selected subset of entire map data available by selecting map data tiles corresponding to an area that encompasses a route. An amount of map data accessed may be adjusted based on a priority assigned to areas or points along the route. A sequence of map data may be accessed based on a priority assigned to sets of map data.

Claims

1. A computer-implemented method for pre-fetching map data for a route in response to an initiation of a routing function of a mapping application, comprising:

initiating a first routing function, using a computer, to generate a route, the route defined by an origin, a destination, and a set of paths connecting the origin to the destination;

determining, using the computer, a first tile radius associated with the origin wherein the first tile radius defines a first set of map data tiles of a first zoom level corresponding to a first map surface area around and including the origin;

determining, using the computer, a second tile radius associated with the destination, wherein the second tile radius defines a second set of map data tiles of the first zoom level corresponding to a second map surface area around and including the destination;

determining, using the computer, a set of points along the route between the origin and the destination and a set of map tile radii for the set of points, wherein the set of map tile radii define a third set of map data tiles of the first zoom level corresponding to a set of map surface areas around and including the set of points along the route, wherein at least one of the first tile radius, the second tile radius, and one of the set of map tile radii are different from each other;

determining, using the computer, a fourth set of map data tiles of a second zoom level different than the first zoom level, wherein the fourth set of map data tiles are defined by at least one of the first tile radius, the second tile radius, or one of the set of map tile radii, and wherein the fourth set of map data tiles provides a different magnification of corresponding map areas than the first, the second, or the third map data tiles;

retrieving from an external map database the first, the second, the third and the fourth sets of map data tiles, wherein the map database stores a plurality of map data tiles, and the first, the second, the third and the fourth sets of map data tiles comprise a subset of the plurality of map data tiles of the map database;

storing the first, the second, the third and the fourth set of map data tiles in a local memory as a first, a second, a third and a fourth set of pre-fetch map data tiles, respectively, wherein the local memory is different from the map database;

initiating a first rendering function to display at least a portion of the route at the first zoom level using at least one of the first, second, or the third set of pre-fetched map data tiles of the local memory instead of map data tiles of the external map database; and

initiating a second rendering function to display at least a portion of the route at the second zoom level using the fourth set of pre-fetched map data tiles of the local memory instead of map data tiles of the external map database, wherein the fourth set of map data tiles is retrieved from the external map database and stored in the local memory prior to initiating the first rendering function.

2. The computer-implemented method of claim 1, wherein each of the first set of map tile radii is determined so that points along the route closer to the origin and destination have shorter radii than points along the route further from the origin and destination.

3. The computer-implemented method of claim 1, wherein one of the set of points along the route corresponds to a location on the route of high priority, and wherein a map tile radii corresponding to the point of high priority is larger than a point of low priority.

4. The computer-implemented method of claim 1, wherein determining the first, the second, and each of the first set of map tile radii is based on an allocated memory size of the client device.

5. The computer-implemented method of claim 1, further including determining that at least one of the first tile radius, the second tile radius and one of the first set of map tile radii is larger when a viewing window is centered on one of the first tile radius, the second tile radius or one of the first set of map tile radii.

6. The computer-implemented method of claim 1, wherein the fourth set of map data tiles are defined by a point along the route when that is within a threshold distance of a viewing window center.

7. The computer-implemented method of claim 1, further including determining, using the computer, a fourth tile radius associated with a point of interest not along the route and wherein the fourth tile radius defines a fourth set of map data tiles corresponding to a location not along the route with high priority, accessing from the map database the fourth set of map data tiles, and storing the fourth set of map data tiles in the local memory as a fourth set of pre-fetch map data tiles, wherein initiating the second rendering function uses the fourth set of pre-fetch map data tiles.

8. The computer-implemented method of claim 1, further including determining the first tile radius, the second tile radius, and the first set of map tile radii to be smaller when a bandwidth of the client device is below a threshold than when the bandwidth is above the threshold and to be smaller when a processor load of the client device is above a threshold than when the processor load is below the threshold.

9. A computer device comprising:

a communications network interface;

one or more processors;

one or more memories coupled to the one or more processors;

a display device coupled to the one or more processors;

wherein the one or more memories include computer executable instructions stored therein that, when executed by the one or more processors, cause the one or more processors to

initiating a first routing function, using a computer, to generate a first route, the first route defined by an origin, a destination, and a set of paths connecting the origin to the destination;

determine a first set of map tile radii associated with a set of points along the first route including the origin and the destination, wherein first set of map tile radii define a first set of map data tiles at a first zoom level corresponding to map surface areas around and including the first route;

determine a second set of map data tiles at a second zoom level different than the first zoom level, wherein the second set of map data tiles are defined by at least one of the first set of map tile radii wherein the second set of map data tiles provides a different magnification of corresponding map areas than the first set of map data tiles;

retrieve from an external map database the first set of map data tiles and the second set of map data tiles, wherein the map database stores the map data as a plurality of map data tiles, and the first set of map data tiles and the second set of map data tiles comprise a subset of the plurality of map data tiles of the map database;

store the first set of map data tiles and the second set of map data tiles in a local memory as a first set and a second set of pre-fetched map data tiles, respectively, wherein the local memory is different from the map database;

initiating a first rendering function to display at least a portion of the first route using the first set of pre-fetched map data tiles of the local memory instead of map data tiles of the external map database; and

initiating a second rendering function to display at least a portion of the route at the second zoom level using the second set of pre-fetched map data tiles, wherein the second set of map data tiles is retrieved from the external map database and stored in the local memory prior to initiating the first rendering function.

10. The computer device of claim 9, further including instructions to determine the first set of pre-fetched map data tiles at a first zoom level to correspond with an area that completely encompasses the entire route and that is displayable within a single viewing window at a first zoom level.

11. The computer device of claim 9, further including a second routing function to generate a second route that includes an origin, a destination, and a set of paths connecting the origin and the destination of the second route;

determine a third set of map tile radii associated with a set of points along the second route including the origin and the destination of the second route, wherein third set of map tile radii define a third set of map data tiles corresponding to map surface areas around and including the second route;

access, from a map database, the third set of map data tiles corresponding to the second route, wherein the map database stores the map data as a plurality of map data tiles, and the third set of map data tiles comprises a subset of the plurality of map data tiles of the map database; and

store the third set of map data tiles in the local memory as a third set of pre-fetched map data tiles, wherein initiating the rendering function uses the third set of pre-fetched map data tiles instead of map data tiles of the map database.

12. The computer device of claim 11, wherein the second route is a return route of the first route and wherein the origin of the first route is the destination of the second route and the destination of the first route is the origin of the second route.

13. The computer device of claim 11, wherein the origin of the second route is along the first route and the destination of the second route is a point of interest within the vicinity of the first route.

14. A computer device comprising:

a communications network interface;

one or more processors;

one or more memories coupled to the one or more processors;

a display device coupled to the one or more processors;

wherein the one or more memories include computer executable instructions stored therein that, when executed by the one or more processors, cause the one or more processors to;

initiate a routing function, using a computer, to generate a route, the route defined by an origin, a destination, and a set of paths connecting the origin to the destination;

determine a first set of map data tiles at a first zoom level corresponding to a first map surface area around and including the origin, a second set of map data tiles at the first zoom level corresponding to a second map surface area around and including the destination, a third set of map data tiles at the first zoom level corresponding to a third map surface area around the route between the origin and the destination, wherein a route map surface area includes the first map area around and including the origin, the second map area around and including the destination and the third map surface area around and including the route;

determine a fourth set of map data tiles at a second zoom level different than the first zoom level, wherein the fourth set of map data tiles correspond to an area along the route, and wherein the fourth set of map data tiles provides a different magnification of the corresponding map area than the first, the second, or the third map data tiles;

retrieve from an external map database, the first set, the second set, third and the fourth set of map data tiles, wherein the map database stores the map data as a plurality of map data tiles, and the first, second, third and fourth set of map data tiles comprise a subset of the plurality of map data tiles of the map database;

store the first set, the second set, third and the fourth set of map data tiles in a local memory as a first, a second, third and a fourth set of pre-fetched map data tiles, respectively, wherein the local memory is different from the map database;

initiate a first rendering function to display at least a portion of the route at the first zoom level using at least one of the first, second, or the third set of pre-fetched map data tiles of the local memory instead of map data tiles of the map database; and

initiate a second rendering function to display at least a portion of the route at the second zoom level using the fourth set of pre-fetched map data tiles of the local memory instead of map data tiles of the external map database, wherein the fourth set of map data tiles is retrieved from the external map database and stored in the local memory prior to initiating the first rendering function.

15. The computer device of claim 14, further including instructions to retrieve, from the map database, the first set, the second set, the third set and the fourth set of map data tiles in a sequence based on a current bandwidth of communications between the computer device and a server.

16. The computer device of claim 14, further including instructions to determine an amount of the first, the second, and the third set of map data tiles to retrieve from the map database based on a current bandwidth of communications between the computer device and a server.