US 12,001,459 B2Granted

Topological basemodel supporting improved conflation and stable feature identity

AssigneeGoogle Inc.

InventorsChristine McGavran, Richard William Bukowski, Bryan Klingner, Joakim Kristian Olle Arfvidsson, Andrew Lookingbill

Life of this patent

Estimating the term…

patentgrep

Loading patent…

Abstract

The present disclosure is directed to systems and methods for providing a stable topological representation of pathway networks as well as features associated with these networks. The disclosure is exemplified using road networks which have applications in mapping, navigation, and autonomous vehicles. Extensions may be learned through practice of the disclosure. Utilizing implementations disclosed herein may provide advantages for data conflation between different mapping systems and map data while improving overall stability by developing a common reference standard that is tied to semantic features rather than abstract geographic representations.

Claims20

Dependent claims

A computing system, comprising:

one or more non-transitory computer-readable media configured to store data and instructions, the data including a shared topological basemodel that comprises a plurality of stable identifiers respectively for a plurality of canonical graph elements that correspond to a plurality of semantic features included in a geographic area;
and
one or more processors configured to execute the instructions to perform operations, the operations comprising:
determining, based at least in part on a common reference to one of the plurality of stable identifiers in the shared topological basemodel, a correspondence between a first graph element among a first plurality of graph elements included in a first geographic dataset and a second graph element among a second plurality of graph elements included in a second geographic dataset, different from the first geographic dataset, wherein the first graph element and second graph element correspond to a same semantic feature among the plurality of semantic features,
identifying a third graph element from among the first plurality of graph elements which lacks a corresponding graph element among the second plurality of graph elements,
in response to identifying the third graph element, generating a fourth graph element which corresponds to the third graph element based on the correspondence between the first graph element and the second graph element, the fourth graph element being provided with a location defined relative to the second graph element, and
adding the fourth graph element to the second geographic dataset to update the second geographic dataset.

4 more elements

A computing system, comprising:

one or more non-transitory computer-readable media configured to store instructions and to store data, a hierarchical database, the hierarchical database including:
a graph including a plurality of graph elements, the plurality of graph elements including one or more anchors, one or more vertices, and one or more edges, wherein each edge, each vertex, and each anchor includes a unique and stable identifier (ID),
a first property layer comprising one or more first attributes, wherein each of the one or more first attributes is indexed to one of the anchors, one of the vertices, one of the edges, or a combination thereof, and
a second property layer comprising one or more second attributes, wherein each of the one or more second attributes is indexed to one of the anchors, one of the vertices, one of the edges, one of the first attributes, or a combination thereof;
and
one or more processors configured to execute the instructions to perform operations, the operations comprising:
updating the hierarchical database by:
associating a death time with a first graph element from among the plurality of graph elements, and
deleting the first graph element according to the death time associated with the first graph element.

6 more elements

Dependencies are inferred from the claim text.

Facts

Application: 18/091,953Filed 30 Dec 2022 · continuation
Published: US 2023/0132820 A14 May 2023
Granted: 4 Jun 2024
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

G06F 16/29
Of structured data, e.g. relational data: geographical information databases
G01C 21/367
Display of a road map: details, e.g. road map scale, orientation, zooming, illumination, level of detail, scrolling of road map or positioning of…
G01C 21/3878
Organisation of map data, e.g. version management or database structures: hierarchical structures, e.g. layering
G06F 16/2272
Indexing structures: management thereof

Family

PCT/US2020/020618Parent of this continuation · filed 2 Mar 2020
US 2023/0132820 A1Pre-grant publication · published 4 May 2023
Application17/251,071Parent of this continuation
US 11,544,299 B2Parent of this continuation
US 2022/0050860 A1Published application
US 12,001,459 B2This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key