Detecting defects in map data

Abstract

A network system evaluates candidate GPS routes with respect to map routes that are based on ground truth map data to identify defects in the ground truth map data. Defects in the ground truth map data may include inconsistencies between various attributes of the map data and the actual road network represented by the candidate GPS routes under evaluation. The network system corrects the identified feedback to ensure that the ground truth map data accurately reflects the attributes of the actual road network.

We claim: 
     
         1 . A computer-implemented method for detecting defects in map data, the method comprising:
 storing ground truth map data describing a road network in a map database;   storing a plurality of global positioning system (GPS) routes;   identifying a candidate GPS route from the plurality of GPS routes for examination, the candidate GPS route indicative of a route driven by a vehicle from a starting location to a destination location;   identifying defects in the ground truth map data based on a comparison of the candidate GPS route and the ground truth map data;   updating the ground truth map data to fix the identified defects;   receiving a request from a device for directions from a requested starting location to a requested destination location;   determining a route from the requested starting location to the requested destination location based on the updated ground truth map data responsive to the request; and   providing the requested directions including the determined route to the device.   
     
     
         2 . The computer-implemented method of  claim 1 , wherein identifying defects in the ground truth map data include:
 identifying a road included in the candidate GPS route that is not included in the ground truth map data   
     
     
         3 . The computer-implemented method of  claim 2 , wherein the ground truth data is updated to include the identified road. 
     
     
         4 . The computer-implemented method of  claim 3 , wherein the determined route from the requested starting location to the requested destination location includes the identified road. 
     
     
         5 . The computer-implemented method of  claim 1 , further comprising:
 determining a distance from the starting location to the destination location and a travel time from the starting location to the destination location using the candidate GPS route;   determining a distance from the starting location to the destination location and a travel time from the starting location to the destination location using the map route; and   comparing the determined distance and travel time from the starting location to the destination location using the candidate GPS route with the determined distance and travel time from the starting location to the destination location using the map route; and   determining that the candidate GPS route is more efficient that the map route based on the comparison.   
     
     
         6 . The computer-implemented method of  claim 5 , further comprising:
 matching the candidate GPS route to a plurality of road segments in the road network as described by the ground truth map data responsive to determining that the candidate GPS route is more efficient than the map route.   
     
     
         7 . The computer-implemented method of  claim 6 , wherein matching the candidate GPS route comprises:
 determining a plurality of GPS points from the candidate GPS route;   determining a plurality of location points from the ground truth map data that corresponds to the plurality of GPS points described by the candidate GPS route, each of the plurality of location points corresponding to one of the plurality of GPS points;   determining the plurality of road segments that correspond to the plurality of location points; and   determining a path of travel that is indicative of an ordering of the plurality of road segments based on the plurality of location points.   
     
     
         8 . The computer-implemented method of  claim 7 , wherein each of the plurality of road segments is associated with a plurality of attributes that describe the road segment in the ground truth map data, the plurality of attributes for each road segment including a geometry of the road segment, a directionality of the road segment, a turn restriction associated with the road segment, and a speed limit of the road segment. 
     
     
         9 . The computer-implemented method of  claim 8 , wherein determining the path of travel comprises:
 ignoring the attributes of the plurality of road segments; and   determining the path of travel such that a geometric shape of the path of travel is consistent with a geometric shape of the candidate GPS route based on the ignored attributes.   
     
     
         10 . The computer-implemented method of  claim 8 , wherein identifying defects in the ground truth map data comprises:
 comparing the plurality of attributes associated with each of the plurality of road segments from the ground truth map data with a plurality of attributes of a portion of the candidate GPS route that corresponds to the road segment;   determining at least one attribute of the map data for a road segment from the plurality of road segments that is inconsistent with a corresponding one of the plurality of attributes of the portion of the candidate GPS route that corresponds to the road segment; and   establishing the at least one attribute of the road segment as a defect in the map data.   
     
     
         11 . A computer program product comprising a non-transitory computer readable storage medium storing executable code for detecting defects in map data, the code when executed by one or more computer processors causes the one or more computer processors to perform steps comprising:
 storing ground truth map data describing a road network in a map database;   storing a plurality of global positioning system (GPS) routes;   identifying a candidate GPS route from the plurality of GPS routes for examination, the candidate GPS route indicative of a route driven by a vehicle from a starting location to a destination location;   identifying defects in the ground truth map data based on a comparison of the candidate GPS route and the ground truth map data;   updating the ground truth map data to fix the identified defects;   receiving a request from a device for directions from a requested starting location to a requested destination location;   determining a route from the requested starting location to the requested destination location based on the updated ground truth map data responsive to the request; and   providing the requested directions including the determined route to the device.   
     
     
         12 . The computer program product of  claim 11 , wherein identifying defects in the ground truth map data include:
 identifying a road included in the candidate GPS route that is not included in the ground truth map data   
     
     
         13 . The computer program product of  claim 12 , wherein the ground truth data is updated to include the identified road. 
     
     
         14 . The computer program product of  claim 13 , wherein the determined route from the requested starting location to the requested destination location includes the identified road. 
     
     
         15 . The computer program product of  claim 11 , further comprising:
 determining a distance from the starting location to the destination location and a travel time from the starting location to the destination location using the candidate GPS route;   determining a distance from the starting location to the destination location and a travel time from the starting location to the destination location using the map route; and   comparing the determined distance and travel time from the starting location to the destination location using the candidate GPS route with the determined distance and travel time from the starting location to the destination location using the map route; and   determining that the candidate GPS route is more efficient that the map route based on the comparison.   
     
     
         16 . The computer program product of  claim 15 , wherein the code when executed by the one or more computer processors cause the one or more computer processors to perform further steps comprising:
 matching the candidate GPS route to a plurality of road segments in the road network as described by the ground truth map data responsive to determining that the candidate GPS route is more efficient than the map route.   
     
     
         17 . The computer program product of  claim 16 , wherein matching the candidate GPS route comprises:
 determining a plurality of GPS points from the candidate GPS route;   determining a plurality of location points from the ground truth map data that corresponds to the plurality of GPS points described by the candidate GPS route, each of the plurality of location points corresponding to one of the plurality of GPS points;   determining the plurality of road segments that correspond to the plurality of location points; and   determining a path of travel that is indicative of an ordering of the plurality of road segments based on the plurality of location points.   
     
     
         18 . The computer program product of  claim 17 , wherein each of the plurality of road segments is associated with a plurality of attributes that describe the road segment in the ground truth map data, the plurality of attributes for each road segment including a geometry of the road segment, a directionality of the road segment, a turn restriction associated with the road segment, and a speed limit of the road segment. 
     
     
         19 . The computer program product of  claim 18 , wherein identifying defects in the ground truth map data comprises:
 comparing the plurality of attributes associated with each of the plurality of road segments from the ground truth map data with a plurality of attributes of a portion of the candidate GPS route that corresponds to the road segment;   determining at least one attribute of the map data for a road segment from the plurality of road segments that is inconsistent with a corresponding one of the plurality of attributes of the portion of the candidate GPS route that corresponds to the road segment; and   establishing the at least one attribute of the road segment as a defect in the map data.   
     
     
         20 . A system for detecting defects in map data, the system comprising:
 a non-transitory computer-readable storage medium storing executable code; and   one or more computer processors configured to execute the code which causes the one or more computer processors to perform steps comprising:
 storing ground truth map data describing a road network in a map database; 
 storing a plurality of global positioning system (GPS) routes; 
 identifying a candidate GPS route from the plurality of GPS routes for examination, the candidate GPS route indicative of a route driven by a vehicle from a starting location to a destination location; 
 identifying defects in the ground truth map data based on a comparison of the candidate GPS route and the ground truth map data; 
 updating the ground truth map data to fix the identified defects; 
 receiving a request from a device for directions from a requested starting location to a requested destination location; 
 determining a route from the requested starting location to the requested destination location based on the updated ground truth map data responsive to the request; and 
 providing the requested directions including the determined route to the device.