Map data validation using knowledge graphs and randomness measures
Systems and methods are disclosed for improved mapping data validation using randomness measures. Methods may include receiving a map dataset that includes a plurality of map features. A knowledge graph may be generated based on the map dataset that may include nodes representing or corresponding to the map features. Nodes corresponding to map features of a particular feature type may be identified and edges connected to the identified nodes may be processed to identify a plurality of paths. A randomness measure for the particular feature type may be determined based on the plurality of paths. The randomness measure may indicate a predictability of occurrences of map features of the particular feature type in the map dataset. The randomness measure may then be compared to a second randomness measure determined based on another map dataset.
1. A method comprising:
receiving a new map dataset associated with operation of a vehicle, wherein the new map dataset includes a plurality of new map features relative to a previous map dataset;
generating, based on the new map dataset, a knowledge graph comprising a plurality of nodes reflecting the plurality of new map features;
determining one or more traversal paths along nodes and edges within the knowledge graph based on the plurality of nodes reflecting the plurality of new map features;
generating, based on the one or more traversal paths within the knowledge graph, a first entropy score for the plurality of new map features;
determining a second entropy score for a previous knowledge graph corresponding to the previous map dataset;
generating a randomness difference between the knowledge graph and the previous knowledge graph by comparing the first entropy score with the second entropy score; and
based on determining that the randomness difference satisfies a predetermined threshold, incorporating the plurality of new map features in generating a production map dataset.
2. The method of claim 1 , further comprising:
determining that a difference between a third entropy score of an additional map dataset and a fourth entropy score of the production map dataset fails to satisfy the predetermined threshold; and
excluding an additional plurality of new map features from the production map dataset.
3. The method of claim 1 , further comprising:
receiving the new map dataset from a map data provider;
determining an accuracy score corresponding to the map data provider based on the randomness difference between the first entropy score and the second entropy score; and
generating, based on the accuracy score, an accuracy profile associated with the map data provider.
4. The method of claim 1 , wherein generating a knowledge graph based on the new map dataset further comprises:
identifying the plurality of new map features within the new map dataset;
determining one or more relationships between the plurality of new map features;
generating, for each of the plurality of new map features, a node in the knowledge graph; and
generating, for each relationship of the one or more relationships, an edge between two corresponding nodes of the knowledge graph.
5. The method of claim 4 , wherein the edges of the knowledge graph designate a relationship type of each relationship between connected nodes.
6. The method of claim 5 , wherein the edge is stored as a triple comprising an identification of a first node connected by the edge, an identification of a second node connected by the edge, and a relationship type of a relationship between the first node and the second node.
7. The method of claim 1 , wherein generating the first entropy score comprises determining information entropy between a starting node and an ending node for a traversal path of the one or more traversal paths.
8. A system comprising:
one or more processors; and
a memory coupled to the one or more processor, the memory comprising instructions, which when executed by the one or more processors, cause the system to:
receive a new map dataset associated with operation of a vehicle, wherein the new map dataset includes a plurality of new map features relative to a previous map dataset;
generate, based on the new map dataset, a knowledge graph comprising a plurality of nodes reflecting the plurality of new map features;
determine one or more traversal paths along nodes and edges within the knowledge graph based on the plurality of nodes reflecting the plurality of new map features;
generate, based on the one or more traversal paths within the knowledge graph, a first entropy score for the plurality of new map features;
determine a second entropy score for a previous knowledge graph corresponding to the previous map dataset;
generate a randomness difference between the knowledge graph and the previous knowledge graph by comparing the first entropy score with the second entropy score; and
based on determining that the randomness difference satisfies a predetermined threshold, incorporate the plurality of new map features in generating a production map dataset.
9. The system of claim 8 , wherein the memory comprises further instruction which, when executed by the one or more processors, cause the system to:
determine that a difference between a third entropy score of an additional map dataset and a fourth entropy score of the production map dataset fails to satisfy the predetermined threshold; and
exclude an additional plurality of new map features from the production map dataset.
10. The system of claim 8 , wherein the memory comprises further instructions which, when executed by the one or more processors, cause the system to:
receive the new map dataset from a map data provider;
determine an accuracy score corresponding to the map data provider based on the randomness difference between the first entropy score and the second entropy score; and
generate, based on the accuracy score, an accuracy profile associated with the map data provider.
11. The system of claim 8 , wherein the memory comprises further instructions which, when executed by the one or more processors cause the system to:
identify the plurality of new map features within the new map dataset;
determine one or more relationships between the plurality of new map features;
generate, for each of the plurality of new map features, a node in the knowledge graph; and
generate, for each relationship of the one or more relationships, an edge between two corresponding nodes of the knowledge graph.
12. The system of claim 11 , wherein the edges of the knowledge graph designate a relationship type of each relationship between connected nodes.
13. The system of claim 12 , wherein the edge is stored as a triple comprising an identification of a first node connected by the edge, an identification of a second node connected by the edge, and a relationship type of a relationship between the first node and the second node.
14. The system of claim 8 , wherein the memory comprises further instruction which, when executed by the one or more processors, cause the system to generate the first entropy score by determining information entropy between a starting node and an ending node for a traversal path of the one or more traversal paths.
15. A non-transitory computer readable storage medium comprising instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising:
receiving a new map dataset associated with operation of a vehicle, wherein the new map dataset includes a plurality of new map features relative to a previous map dataset;
generating, based on the new map dataset, a knowledge graph comprising a plurality of nodes reflecting the plurality of new map features;
determining one or more traversal paths along nodes and edges within the knowledge graph based on the plurality of nodes reflecting the plurality of new map features;
generating, based on the one or more traversal paths within the knowledge graph, a first entropy score for the plurality of new map features;
determining a second entropy score for a previous knowledge graph corresponding to the previous map dataset;
generating a randomness difference between the knowledge graph and the previous knowledge graph by comparing the first entropy score with the second entropy score; and
based on determining that the randomness difference satisfies a predetermined threshold, incorporating the plurality of new map features in generating a production map dataset.
16. The non-transitory computer readable storage medium of claim 15 , wherein the operations further comprise:
determining that a difference between a third entropy score of an additional map dataset and a fourth entropy score of the production map dataset fails to satisfy the predetermined threshold; and
excluding an additional plurality of new map features from the production map dataset.
17. The non-transitory computer readable storage medium of claim 15 , wherein the operations further comprise:
receiving the new map dataset from a map data provider;
determining an accuracy score corresponding to the map data provider based on the randomness difference between the first entropy score and the second entropy score; and
generating, based on the accuracy score, an accuracy profile associated with the map data provider.
18. The non-transitory computer readable storage medium of claim 15 , wherein the operations further comprise generating the knowledge graph based on the new map dataset by:
identifying the plurality of new map features within the new map dataset;
determining one or more relationships between the plurality of new map features;
generating, for each of the plurality of new map features, a node in the knowledge graph; and
generating, for each relationship of the one or more relationships, an edge between two corresponding nodes of the knowledge graph.
19. The non-transitory computer readable storage medium of claim 18 , wherein the edge is stored as a triple comprising an identification of a first node connected by the edge, an identification of a second node connected by the edge, and a relationship type of a relationship between the first node and second node.
20. The non-transitory computer readable storage medium of claim 15 , wherein generating the first entropy score comprises determining information entropy between a starting node and an ending node for a traversal path of the one or more traversal paths.