Adaptive geographical data caching based on a route pattern

Patent metadata

Field	Value
Publication number	US-11003696-B2
Application number	US-201816023594-A
Country	US
Kind code	B2
Filing date	Jun 29, 2018
Priority date	Jun 29, 2018
Publication date	May 11, 2021
Grant date	May 11, 2021

Abstract

Various embodiments partition map data into discrete portions of map data based on predetermined boundaries, and individual map data portions (e.g., shards) are assigned to individual computing nodes in a plurality of computing nodes that service geographic routing requests. A routing component associated with the plurality of computing nodes directs the geographic routing request to one or more computing nodes. The computing nodes adaptively cache geographical map data based on, for example, data relating to past geographic routes. Once cached at a computing node in a plurality of computing nodes, the computing node services current and future geographic routing requests using its assigned portion of map data and one or more portions of map data adaptively cached at the computing node, thereby reducing chances of more than one computing node getting involved in servicing a request.

First claim

What is claimed is:

1. A system comprising:
a plurality of computing nodes for servicing geographic routing requests between origin locations and destination locations, each individual computing node in the plurality of computing nodes comprising a cache and being assigned a portion of map data for servicing geographic routing requests that are routed from a client device to the individual computing node; and
a request routing module configured to receive an individual geographic routing request from a client device and route the individual geographic routing request to a select computing node in the plurality of computing nodes, and the select computing node being configured to perform operations comprising:
loading an assigned portion of map data for use, by the select computing node, in servicing geographic routing requests received by the select computing node from the request routing module, the assigned portion of map data being assigned to the select computing node;
receiving, from the request routing module, a particular geographic routing request between a particular origin location covered by the assigned portion of map data and a particular destination location, the particular geographic routing describing the particular origin location and the particular destination location;
analyzing the particular geographic routing request to determine whether the particular geographic routing request involves map data not included by the assigned portion of map data;
in response to determining that the particular geographic routing request involves map data not included by the assigned portion of map data, requesting, from the cache of the select computing node, additional map data for the particular geographic routing request, the additional map data being different from the assigned portion of map data;
generating, based on the particular geographic routing request, a geographic route using the assigned portion of map data and the additional map data; and
responding to the particular geographic request by providing the generated geographic route to the client device.

2. The system of claim 1 , wherein the operations further comprise:
determining whether the requesting the additional map data from the cache results in a cache miss; and
in response to determining that the requesting the additional map data from the cache results in the cache miss, accessing the additional map data from a data source external from the computing node.

3. The system of claim 1 , wherein the assigned portion comprises a map data shard.

4. The system of claim 1 , wherein the particular geographic routing request is directed to the computing node based on the assigned portion of map data.

5. The system of claim 1 , wherein the additional map data comprises a second portion of map data that includes a given origin location or a given destination location associated with the particular geographic route request.

6. The system of claim 5 , wherein the additional map data further comprises a minimum number of other portions of map data that surround the second portion of map data.

7. The system of claim 1 , wherein the operations comprise:
accessing historical geographic route data describing one or more geographic routes generated in the past;
identifying the additional map data based on the accessed historical geographic route data, the additional map data being different from the assigned portion of map data; and
storing the additional map data to the cache of the select computing node.

8. A method comprising:
loading, at a computing node, an assigned portion of map data for use, by the computing node, in servicing geographic routing requests received by the computing node from a request routing module, the assigned portion of map data being assigned to the computing node, and the request routing module configured to receive an individual geographic routing request from a client device and route the individual geographic routing request to the computing node;
accessing, at the computing node, historical geographic route data describing one or more geographic routes generated in the past;
identifying, at the computing node, additional map data based on the accessed historical geographic route data, the additional map data being different from the assigned portion of map data;
accessing, at the computing node, the additional map data from a data source external to the computing node;
receiving, from the request routing module, a particular geographic routing request between a particular origin location covered by the assigned portion of map data and a particular destination location, the particular geographic routing describing the particular origin location and the particular destination location;
generating, based on the particular geographic routing request, a geographic route using the assigned portion of map data and the additional map data; and
responding to the particular geographic request by providing the generated geographic route to the client device.

9. The method of claim 8 , wherein the identifying the additional map data based on the accessed historical geographic route data comprises:
determining, based on the accessed historical geographic route data, a set of destination locations visited from a set of origin locations covered by the assigned portion of map data, the additional map data at least covering a set of routes from the one or more origin locations to the set of destination locations.

10. The method of claim 8 , wherein the assigned portion comprises a map data shard.

11. The method of claim 8 , further comprising:
storing the additional map data to a cache of the computing node.

12. The method of claim 11 , further comprising:
analyzing the particular geographic routing request to determine whether the particular geographic routing request involves map data not included by the assigned portion of map data; and
in response to determining that the particular geographic routing request involves map data not included by the assigned portion of map data, requesting, from the cache, particular map data that covers at least one route from the particular origin location to the particular destination location, the particular map data being different from the assigned portion of map data.

13. The method of claim 12 , wherein the particular destination location is included in a set of destination locations, the set of destination locations visited from a set of origin locations covered by the assigned portion of map data, and the method further comprises:
in response to the requesting the particular map data from the cache:
determining whether the particular map data is stored in the cache; and
in response to the determining that the particular map data is stored in the cache, accessing the particular map data from the additional map data stored on the cache.

14. The method of claim 12 , further comprising:
determining whether the requesting the particular map data from the cache results in a cache miss; and
in response to determining that the requesting the particular map data from the cache results in the cache miss, accessing the particular map data from a data source external from the computing node.

15. The method of claim 8 , wherein the computing node is part of a plurality of computing nodes for servicing geographic routing requests between origin locations and destination locations, each computing node in the plurality of computing nodes being assigned a portion of map data for servicing a geographic routing request.

16. A non-transitory computer storage medium

Assignees

• Uber Technologies Inc

Inventors

• Hu Norbert Y
• Lien Calvin Shawn
• Donovan Brian Patrick
• Hamby Brent Evans

Classifications

• H04L67/568

  Storing data temporarily at an intermediate stage, e.g. caching · CPC title

• H04L67/52

  specially adapted for the location of the user terminal · CPC title

• H04W4/024

  Guidance services · CPC title

• H04L67/1021

  based on client or server locations · CPC title

• H04L67/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] · CPC title