Adaptive geographical data caching based on a route pattern

Patent metadata

Field	Value
Publication number	US-2020004844-A1
Application number	US-201816023594-A
Country	US
Kind code	A1
Filing date	Jun 29, 2018
Priority date	Jun 29, 2018
Publication date	Jan 2, 2020
Grant date	—

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 computing node in the plurality of computing nodes being assigned a portion of map data for servicing a geographic routing request, a computing node in the plurality of computing nodes comprising a cache, the computing node performing operations comprising:
loading an assigned portion of map data for use, by the computing node, in servicing a received geographic routing request;
receiving a particular geographic routing request;
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, additional map data for the particular geographic routing request, the additional map data being different from the assigned portion of map data.

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 operations further comprise:
generating, based on the particular geographic request, a geographic route using the assigned portion of map data and the additional map data; and responding to the particular geographic request with the generated geographic route.

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

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

8 . A method comprising:
loading, at a computing node, an assigned portion of map data for use, by the computing node, in servicing a received geographic routing request; 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; and accessing, at the computing node, the additional map data from a data source external to the computing node.

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 at the computing node.

12 . The method of claim 11 , further comprising:
receiving, at the computing node, a particular geographic routing request between a particular origin location covered by the assigned portion of map data and a 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; 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 the set of destination locations, 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 comprising instructions that, when executed by one or more hardware processors of a computing node, cause the computing node to perform operations comprising:
loading an assigned portion of map data for use, by the computing node, in servicing a received geographic routing request; accessing, from a data source external to the computing node, additional map data based on the assigned portion of the map data; and storing the additional map data to a cache at the computing node.

17 . The non-transitory computer storage medium of claim 16 , wherein the accessing the additional map data based on the assigned portion of the map data comprises:
identifying map data falling within a boundary of a geometric shape positioned relative to the assigned portion of map data, the additional map data comprising the identified map data.

18 . The non-transitory computer storage medium of claim 16 , wherein the accessing the additional map data based on the assigned portion of the map data comprises accessing a set of portions of map data associated with the assigned portion of data.

19 . The non-transitory computer storage medium of claim 16 , wherein the assigned portion comprises a map data shard.

20 . The non-transitory computer storage medium of claim 16 , wherein the operations further comprise:
receiving a particular geographic routing request; 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 for the particular geographic routing request, the particular map d

Assignees

• Uber Technologies Inc

Inventors

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

Classifications

• H04W4/024

  Guidance services · CPC title

• H04W4/029

  Location-based management or tracking services · CPC title

• G06F16/29 Primary

  Geographical information databases · CPC title

• G08G1/0968

  Systems involving transmission of navigation instructions to the vehicle · 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