Automated identification of anomalous map data

• US 10,678,776 B1
• Filed: 02/21/2017
• Issued: 06/09/2020
• Est. Priority Date: 10/06/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Kadous, Mohammed Waleed, Arfvidsson, Joakim Kristian Olle, Mantri, Anup
• Primary Examiner(s): Nolan, Peter D
• Application Number:
  US15/438,645
• Time in Patent Office: 1,204 Days
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G01C 21/3815 Road data
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

An autocheck module of a map system is configured to automatically identify anomalous conditions within map data that may indicate an error within the data. The identification of the anomalous conditions is accomplished by application of different autocheck types to the map data, each autocheck type representing a class of anomalies and being triggered if particular map data exhibits the anomalous condition associated with the autocheck type. In one embodiment, for at least some of the portions of map data that trigger an autocheck type, an issue entry is created in an issue database, the issue entry referencing the autocheck type that was triggered, the map data that triggered it, and any associated data of relevance for the particular autocheck type in question.

Claims

1. A computer-implemented method of identifying anomalous conditions in a database of map data, the method comprising:

storing, by a computing system comprising one or more processors, a set of distinct autocheck types, each autocheck type associated with a category of anomalous condition and indicating, when associated with a portion of map data, whether the associated category of anomalous condition is present within the portion, wherein the set of distinct autocheck types comprises a name-property correlation autocheck type;

automatically associating, by the computing system, a plurality of the stored autocheck types to the database of map data,

wherein automatically associating the plurality of the stored autocheck types to the database of map data comprises;

identifying, by the computing system, in the portion of the map data, a road segment, a name of the road segment, and a property value of the road segment;

determining, by the computing system, that an anomalous condition is present in the portion of the map data, responsive to the identified property not corresponding to an expected property value of the identified name of the road segment;

for each applied autocheck type, and for portions of the map data for which the autocheck type indicates that the associated category of anomalous condition is present, determining, by the computing system, based on logs of prior routes requested by users, a plurality of routes between source locations and destination locations associated with a subset of the portion of the map data;

responsive to confirming that the anomalous condition is present, creating, by the computing system, an issue entry associated with the subset of the portion of the map data within which the associated anomalous condition is present; and

displaying, by the computing system, imagery comprising the portion of the map data for which the autocheck type indicates that the associated category of anomalous condition is present.

2. The computer-implemented method of claim 1, wherein the set of distinct autocheck types comprises a misaligned road segments autocheck type, and wherein applying the misaligned road segments autocheck type comprises:

identifying, by the computing system, in the portion of the map data, two consecutive turns defined by road segments within the portion of map data, the turns being within some threshold distance of each other;

determining, by the computing system, an angle of the first turn and an angle of the second turn; and

determining, by the computing system, that an anomalous condition is present in the portion of the map data, responsive to a sum of the angles being within some threshold number of degrees from 180 degrees.

3. The computer-implemented method of claim 1, wherein the set of distinct autocheck types comprises an intersecting roads autocheck type, and wherein applying the intersecting roads autocheck type comprises:

identifying, by the computing system, in the portion of the map data, one of an unexpected presence of an intersection between a first road segment and a second road segment and an unexpected absence of an intersection between the first road segment and the second road segment, the identification performed based on altitudes of the first and second road segments indicated by the map data.

4. The computer-implemented method of claim 3, wherein identifying an unexpected presence of the intersection comprises:

identifying, by the computing system, an intersection between the first road segment and the second road segment in the portion of the map data;

determining, by the computing system, that an anomalous condition is present in the portion of the map data, responsive to determining that an altitude of the first road segment and an altitude of the second road segment are not substantially the same.

5. The computer-implemented method of claim 3, wherein identifying an unexpected absence of the intersection comprises:

identifying, by the computing system, a lack of an intersection between a first road segment and a second road segment in the portion of the map data;

determining, by the computing system, that an anomalous condition is present in the portion of the map data, responsive to determining that an altitude of the first road segment and an altitude of the second road segment are substantially the same.

6. The computer-implemented method of claim 1, wherein the set of distinct autocheck types comprises an intersecting roads autocheck type, and wherein applying the intersecting roads autocheck type comprises:

identifying, by the computing system, an intersection between a first road segment and a second road segment in the portion of the map data; and

determining, by the computing system, that an anomalous condition is present in the portion of the map data, responsive to a road type of the first road segment differing from a road type of the second road segment.

7. The computer-implemented method of claim 1, wherein the set of distinct autocheck types comprises an unreachable clusters autocheck type, and wherein applying the unreachable clusters autocheck type comprises:

obtaining, by the computing system, intersection-oriented map data from the portion of the map data in the database, wherein the intersection-oriented map data comprises nodes corresponding to intersections and edges between the nodes corresponding to road segments between the intersections, each road segment having a first end and a second end;

mapping, by the computing system, the intersection-oriented map data to segment-oriented map data, wherein the segment-oriented map data comprises pairs of nodes, each pair of nodes corresponding to one of the road segments, a first node of a pair representing traversal of the corresponding road segment from the first end of the road segment to the second end of the road segment, and a second node of the pair representing traversal of the corresponding road segment from the second end of the road segment to the first end of the road segment;

performing, by the computing system, a reachability analysis within a graph formed by the segment-oriented map data, the reachability analysis determining based on the map data which road segments a traveler can reach from which other road segments;

identifying, by the computing system, a first road segment of the segment-oriented map data from which it is expected that a traveler could reach a second road segment of the segment-oriented map data; and

determining, by the computing system, that an anomalous condition is present in the portion of the map data, responsive to the reachability analysis indicating that a traveler cannot reach the second road segment from the first road segment.

8. The computer-implemented method of claim 7, wherein identifying the first road segment from which it is expected that a traveler could reach a second road segment comprises determining that the first road segment is less than some threshold distance from the second road segment.

9. The computer-implemented method of claim 7, further comprising performing the reachability analysis separately for each of a plurality of different road types.

10. The computer-implemented method of claim 1, wherein the set of distinct autocheck types comprises a changing properties autocheck type, and wherein applying the changing properties autocheck type comprises:

identifying, by the computing system, in the portion of the map data, a path comprising a set of adjacent road segments; and

determining, by the computing system, that an anomalous condition is present in the portion of the map data, responsive to detecting at least a threshold degree of variation across segments of a property of the road segments in the path.

11. The computer-implemented method of claim 10, wherein the property is one of segment name, segment directionality, and segment priority level.

12. The computer-implemented method of claim 1, wherein the set of distinct autocheck types comprises an access control autocheck type, and wherein applying the access control autocheck type comprises:

identifying, by the computing system, in the portion of the map data, a transition between a first road segment having a first priority level indicating controlled access and a second road segment adjacent to the first road segment and having a second priority level indicating a lack of controlled access;

determining, by the computing system, whether the second road segment corresponds to a ramp; and

determining, by the computing system, that an anomalous condition is present in the portion of the map data, responsive to determining that the second road segment does not correspond to a ramp.

13. The computer-implemented method of claim 1, wherein the set of distinct autocheck types comprises an access control autocheck type, and wherein applying the access control autocheck type comprises:

identifying, by the computing system, in the portion of the map data, a set of road segments that connect to form a cycle; and

determining, by the computing system, that an anomalous condition is present in the portion of the map data, responsive to;

the cycle having less than some threshold length;

a sum of turn angles between the road segments in the cycle being less than some threshold amount; and

the road segments in the cycle not being listed in the map data as being part of a roundabout.

14. The computer-implemented method of claim 1, wherein the set of distinct autocheck types comprises an opposing one-way segments autocheck type, and wherein applying the opposing one-way segments autocheck type comprises:

identifying, by the computing system, in the portion of the map data, a first one-way road segment and a second one-way road segment that are directed in opposite directions and that terminate at a common intersection; and

determining, by the computing system, that an anomalous condition is present in the portion of the map data, responsive to the first one-way road segment and the segment one-way road segment being substantially parallel.

15. The computer-implemented method of claim 1, wherein the set of distinct autocheck types comprises a priority dead-end autocheck type, and wherein applying the priority dead-end autocheck type comprises:

identifying, by the computing system, in the portion of the map data, an intersection, each road segment that enters the intersection, and a priority level of each of the road segments; and

determining, by the computing system, that an anomalous condition is present in the portion of the map data, responsive to a first one of the road segments lacking a corresponding second one of the road segments having at least as high a priority level as the first road segment.

16. The computer-implemented method of claim 1, wherein the set of distinct autocheck types comprises a ramp fork autocheck type, and wherein applying the ramp fork autocheck type comprises:

identifying, by the computing system, in the portion of the map data, a one-way ramp road segment that forks into two one-way road segments; and

determining, by the computing system, that an anomalous condition is present in the portion of the map data, responsive to either of the two one-way road segments not being a ramp.

17. The computer-implemented method of claim 1, wherein the set of distinct autocheck types comprises a ramp connection autocheck type, and wherein applying the ramp connection autocheck type comprises:

identifying, by the computing system, in the portion of the map data, a one-way ramp road segment that forks into two one-way road segments; and

determining, by the computing system, that an anomalous condition is present in the portion of the map data, responsive to neither of the two one-way road segments having a priority level corresponding to an arterial road.

18. The computer-implemented method of claim 1, wherein the set of distinct autocheck types comprises a short segment autocheck type, and wherein applying the short segment autocheck type comprises:

identifying, by the computing system, in the portion of the map data, a road segment and a corresponding priority level of the road segment; and

determining, by the computing system, that an anomalous condition is present in the portion of the map data, responsive to the road segment having a length shorter than a length expected of the corresponding priority level.

19. The computer-implemented method of claim 1, wherein the set of distinct autocheck types comprises a split roads autocheck type, and wherein applying the split roads autocheck type comprises:

identifying, by the computing system, in the portion of the map data, two one-way road segments constituting a split road, the identifying comprising;

identifying, by the computing system, an intersection such that;

one of the two one-way road segments terminates at the intersection,

the other of the two one-way road segments originates at the intersection, and

a two-way road segment joins the intersection;

determining, by the computing system, that an angle between the two one-way road segments is less than a first threshold degree; and

determining, by the computing system, that an angle between the two-way road segment and each of the two one-way road segments is greater than a second threshold degree;

identifying, by the computing system, in the portion of map data, whether U-turns are permitted at the intersection; and

determining, by the computing system, that an anomalous condition is present in the portion of the map data, responsive to U-turns not being permitted at the intersection.

20. The computer-implemented method of claim 1, wherein the set of distinct autocheck types comprises a discontinued one-way autocheck type, and wherein applying the discontinued one-way autocheck type comprises:

identifying, by the computing system, in the portion of the map data, a first road segment and a second road segment that neighbors the first road segment; and

determining, by the computing system, that an anomalous condition is present in the portion of the map data, responsive to the first road segment being one-way and the second road segment not being one-way.

21. The computer-implemented method of claim 1, wherein the set of distinct autocheck types comprises an unreachable clusters autocheck type, and wherein applying the unreachable clusters autocheck type comprises:

obtaining, by the computing system, intersection-oriented map data from the map data in the database, wherein the intersection-oriented map data comprises nodes corresponding to intersections and edges between the nodes corresponding to road segments between the intersections, each road segment having a first end and a second end;

mapping, by the computing system, the intersection-oriented map data to segment-oriented map data, wherein the segment-oriented map data comprises pairs of nodes, each pair of nodes corresponding to one of the road segments, a first node of a pair representing traversal of the corresponding road segment from the first end of the road segment to the second end of the road segment, and a second node of the pair representing traversal of the corresponding road segment from the second end of the road segment to the first end of the road segment;

performing, by the computing system, reachability analysis within a graph formed by the segment-oriented map data, the reachability analysis determining based on the map data which road segments a traveler can reach from which other road segments;

determining, by the computing system, that an anomalous condition is present in the map data, responsive to the reachability analysis indicating either that there is a road segment that cannot be reached from any other road segment, or that there is a road segment that cannot reach any other road segment.

22. The computer-implemented method of claim 1, wherein the identified property value is a priority level of the road segment, the method further comprising:

mapping, by the computing system, the identified name to a class associated with one or more priority levels; and

determining, by the computing system, that an anomalous condition is present in the portion of the map data, responsive to the identified priority level not corresponding to any of the priority levels associated with the class.

23. The computer-implemented method of claim 1, wherein the set of distinct autocheck types comprises an intersection address discrepancy autocheck type, and wherein applying the intersection address discrepancy autocheck type comprises:

identifying, by the computing system, in the portion of the map data, an intersection, a first road segment that joins the intersection, and second road segment that joins the intersection and that has a same name as the first road segment; and

determining, by the computing system, that an anomalous condition is present in the portion of the map data, responsive to at least one of;

address numbers failing to increase in a consistent direction across the first road segment and the second road segment, and

odd-numbered addresses appearing on one side of the first road segment and on a different side of the second road segment.

24. A computing system comprising:

one or more processors;

one or more non-transitory computer-readable media storing instructions that when executed by the one or more processors cause the one or more processors to perform operations comprising;

storing a set of distinct autocheck types, each autocheck type associated with a category of anomalous condition and indicating, when associated with a portion of map data, whether the associated category of anomalous condition is present within the portion, wherein the set of distinct autocheck types comprises a name-property correlation autocheck type;

automatically associating a plurality of the stored autocheck types to the database of map data, wherein automatically associating the plurality of the stored autocheck types to the database of map data comprises;

identifying in the portion of the map data, a road segment, a name of the road segment, and a property value of the road segment;

determining that an anomalous condition is present in the portion of the map data, responsive to the identified property not corresponding to an expected property value of the identified name of the road segment;

for each applied autocheck type, and for portions of the map data for which the autocheck type indicates that the associated category of anomalous condition is present, determining, based on logs of prior routes requested by users, a plurality of routes between source locations and destination locations associated with a subset of the portion of the map data;

responsive to confirming that the anomalous condition is present, creating an issue entry associated with the subset of the portion of the map data within which the associated anomalous condition is present; and

displaying imagery comprising the portion of the map data for which the autocheck type indicates that the associated category of anomalous condition is present.

25. One or more tangible, non-transitory computer-readable media storing computer-readable instructions that when executed by one or more processors cause the one or more processors to perform operations, the operations comprising:

storing a set of distinct autocheck types, each autocheck type associated with a category of anomalous condition and indicating, when associated with a portion of map data, whether the associated category of anomalous condition is present within the portion, wherein the set of distinct autocheck types comprises a name-property correlation autocheck type;

automatically associating a plurality of the stored autocheck types to the database of map data, wherein automatically associating the plurality of the stored autocheck types to the database of map data comprises;

identifying in the portion of the map data, a road segment, a name of the road segment, and a property value of the road segment;

determining that an anomalous condition is present in the portion of the map data, responsive to the identified property not corresponding to an expected property value of the identified name of the road segment;

for each applied autocheck type, and for portions of the map data for which the autocheck type indicates that the associated category of anomalous condition is present, determining, based on logs of prior routes requested by users, a plurality of routes between source locations and destination locations associated with a subset of the portion of the map data;

responsive to confirming that the anomalous condition is present, creating an issue entry associated with the subset of the portion of the map data within which the associated anomalous condition is present; and

displaying imagery comprising the portion of the map data for which the autocheck type indicates that the associated category of anomalous condition is present.