Microsoft Technology Licensing, LLC

Theodoros Gkountouvas

Jan-Ove Almli Karlberg

Anders Tungeland Gjerdrum

Tor Kreutzer

Vincent Mulwa Kyalo

Anthony Acquah

Vincent Macharia Karuri

Iqra Ali

Ronny Jensen

Kai-Marius Pedersen

Solutions are disclosed that enable efficient federated graph queries across multiple isolated data stores. Examples leverage the connectedness of the expected data that spans the data stores by defining the entities and relationships and inferring the intent of the queries. These are used to optimize data searches in the individual data stores. Examples map each of two or more variables of the input query to elements of a public schema and use the mapping to determining a storage tag (identifying a data store) for each of the variables of the input query. Store-specific queries are scheduled and performed based on at least the storage tags.

Federated graph queries across heterogeneous data stores

Example solutions for performing federated graph queries use schemas and include: generating a logical graph using a query input and generating a physical plan using a query planning schema for double-nested loops, the outer loop for each permutation of data stores in a set of data stores, and the inner loop for each data store—ceasing when the logical graph has been fully consumed. A query cost is determined for each of the permutations, and a physical plan is selected based on the query cost, for example minimizing the query cost, and the query is executed based on the selected physical plan. The cost may be determined based on a weighted combination of factors such as freshness of the data, latency, power consumption, environmental impact (e.g., carbon footprint), energy efficiency, and network burden.

Distribution of federated graph queries using schemas

The disclosed technology is generally directed to identification resolution in distributed knowledge graphs. In one example of the technology, a graph query is received. A metagraph includes identifier acceptance information associated with which identifiers among the identifiers are accepted by the data stores in the plurality of data stores and identifier export information associated with which identifiers among the identifiers are exported by the data stores in the plurality of data stores. The metagraph and the cost information are used to select, from among query paths, a query path that is capable of fulfilling the graph query based on minimizing a cost according to a cost metric. Upon determining that a failure has occurred in the selected query path, the metagraph and the cost information are used to change the selected query path. A response to the graph query is provided based on the selected query path.

Identification resolution in distributed knowledge graphs

Growing community of inventors

Tromso, Norway

Theodoros Gkountouvas