Vehicle routing guidance to an authoritative location for a point of interest

Patent metadata

Field	Value
Publication number	US-10480954-B2
Application number	US-201715606555-A
Country	US
Kind code	B2
Filing date	May 26, 2017
Priority date	May 26, 2017
Publication date	Nov 19, 2019
Grant date	Nov 19, 2019

Abstract

An authoritative candidate is selected for determining a location of a point of interest (POI). Source data including name, address, and location for POIs is received from multiple data sources. The received data is normalized for ease of comparison, and coordinates for each candidate are compared to coordinates of other candidates to determine which candidate if any is an authoritative location for the POI. The candidate locations are compared using two models a metric-based scoring system and a machine learning model that may utilize a gradient boosted decision tree. The authoritative candidate can be used to render digital maps that include the POI. In addition, the authoritative candidate's location can be used to provide vehicle route guidance to the POI.

First claim

We claim:

1. A computer-implemented method for providing vehicle routing guidance to a point of interest, comprising:
receiving, by at least one processor from a plurality of data sources, point of interest data including at least one or more candidate locations for the point of interest and identifying information for the point of interest;
obtaining map data including at least locations of road segments in an area surrounding the one or more candidate locations for the point of interest;
for each of the one or more candidate locations:
evaluating for the candidate location, based on the map data and the candidate location, a plurality of metrics, wherein one of the plurality of metrics is an across-the-road consensus metric;
determining a metric score corresponding to each of the plurality of metrics; and
aggregating the metric scores to calculate an aggregate score for the candidate location;

selecting a first candidate location from the one or more candidate locations, the first candidate location having the highest aggregate score of the one or more candidate locations;
providing vehicle routing guidance to the first candidate location.

2. The computer-implemented method of claim 1 , further comprising:
for the one or more candidate locations:
calculating a feature vector for the one or more candidate locations, the feature vector corresponding to the point of interest;
applying a multiclass classifier to the calculated feature vector;
classifying one of the one or more candidate locations as authoritative using the applied classifier; and
calculating a confidence value associated with the classification of the candidate location;
selecting the classified candidate location as a second candidate location from the one or more candidate locations;

selecting an authoritative candidate location from the first selected candidate location and the second selected candidate location, based on the aggregate score of the first candidate location and the associated confidence value of the second candidate location;
providing vehicle routing guidance to the selected authoritative candidate location.

3. The computer-implemented method of claim 2 , wherein the multiclass classifier is a gradient boosted decision tree.

4. The computer-implemented method of claim 3 , wherein the gradient boosted decision tree is trained by:
retrieving training data containing a set of one or more candidate locations for each of a plurality of points of interest and a curated location for each of the plurality of points of interest, wherein each candidate location of each set of one or more candidate locations is associated with a different provider;
obtaining map data including at least road segment data;
for each of the plurality of points of interest in the training data:
applying authority criteria to the set of one or more candidate locations associated with the point of interest;
responsive to determining that a candidate location of the set of one or more candidate locations satisfies the authority criteria, based on the curated location, the set of one or more candidate locations associated with the point of interest, and the map data: selecting the candidate location as a target location for the point of interest; and
responsive to determining that none of the set of one or more candidate locations satisfies the authority criteria, based on the curated location, the set of one or more candidate locations associated with the point of interest, and the map data: indicating that there is no target location for the point of interest; and

applying a gradient boosting algorithm to train the gradient boosted decision tree that optimally classifies candidate locations in a set of one or more candidate locations as target locations or non-target locations for each point of interest in the training data, according to a loss function and a regularization function.

5. The computer-implemented method of claim 2 , wherein the feature vector comprises a plurality of features including per-location features and per-pair features.

6. The computer-implemented method of claim 2 , wherein the multiclass classifier includes multiple binary classifiers associated with each provider of candidate locations.

7. The computer-implemented method of claim 1 , wherein the plurality of metrics further includes at least one of:
a building footprint consensus metric,
a distance from the nearest road metric,
a nearest-same-segment consensus metric, or
a nearest segment popularity metric.

8. A computer program product for providing vehicle routing guidance to a point of interest, the computer program product stored on a non-transitory computer-readable medium and including instructions that when executed cause a processor to carry out steps comprising:
receiving, by at least one processor from a plurality of data sources, point of interest data including at least one or more candidate locations for the point of interest and identifying information for the point of interest;
obtaining map data including at least locations of road segments in an area surrounding the one or more candidate locations for the point of interest;
for the one or more candidate locations:
calculating a feature vector for the one or more candidate locations, the feature vector corresponding to the point of interest;
applying a multiclass classifier to the calculated feature vector;
classifying one of the one or more candidate locations as authoritative using the applied classifier; and
calculating a confidence value associated with the classification of the candidate location;
selecting the classified candidate location as a first candidate location from the one or more candidate locations;

providing vehicle routing guidance to the first candidate location.

9. The computer program product of claim 8 , further comprising:
for each of the one or more candidate locations:
evaluating for the candidate location, based on the map data and the candidate location, a plurality of metrics;
determining a metric score corresponding to each of the plurality of metrics; and
aggregating the metric scores to calculate an aggregate score for the candidate location;

selecting a second candidate location from the one or more candidate locations, the second candidate location having the highest aggregate score of the one or more candidate locations;
selecting an authoritative candidate location from the first selected candidate location and the second selected candidate location, based on the aggregate score of the second candidate location and the associated confidence value of the first candidate location;
providing vehicle routing guidance to the selected authoritative candidate location.

10. The computer program product of claim 9 , wherein the plurality of metrics includes at least one of:
an across-the-road consensus metric,
a building footprint consensus metric,
a distance from the nearest road metric,
a nearest-same-segment consensus metric, or
a nearest segment popularity metric.

11. The computer program product of claim 8 , wherein the multiclass classifier is a gradient boosted decision tree.

12. The computer program product of claim 11 , wherein the gradient boosted decision tree is trained by:
retrieving training data containing a set of one or more candidate locations for each of a plurality of points of interest and a curated location for each of the plurality of points of interest, wherein each candidate location of each set of candidate locations is associated with a different provider;
obtaining map data including at least road segment data;
for each of the plurality of points of i

Assignees

• Uber Technologies Inc

Inventors

• Sheth Chandan Prakash
• Yang Sheng
• Parameswaran Vasudev
• Singh Shivendra Pratap
• Jan Jane Alam

Classifications

• G06N20/20

  Ensemble learning · CPC title

• G06N5/01

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G01C21/3679

  Retrieval, searching and output of POI information, e.g. hotels, restaurants, shops, filling stations, parking facilities (G01C21/3611 takes precedence) · CPC title

• G06F7/20

  Comparing separate sets of record carriers arranged in the same sequence to determine whether at least some of the data in one set is identical with that in the other set or sets · CPC title

• G06F7/023

  adaptive, e.g. self learning · CPC title