Back to results
US 2016/0078148 A1Published application
Estimating similarity of nodes using all-distances sketches
AssigneeMicrosoft Corporation
InventorsRenato F. Werneck, Moises Goldszmidt, Andrew V. Goldberg, Edith Cohen, Daniel Delling, Fabian Fuchs
Life of this patent
Estimating the term…
Abstract
One or more all-distances sketches are generated for nodes in a graph. An all-distances sketch for a node includes a subset of the nodes of the graph, and a shortest distance between the node and each of the nodes in the subset of nodes. The generated all-distances sketches are used to estimate the closeness similarity of nodes. The estimated closeness similarity can be used for targeted advertising or for content item recommendation, for example.
Claims20
A method comprising:
- receiving an indication of a first node and an indication of a second node by a computing device, wherein the first node and the second node are comprised within a plurality of nodes comprising a graph;
- retrieving a plurality of all-distances sketches of the first node and a plurality of all-distances sketches of the second node by the computing device;
- estimating the similarity of the first node and the second node using the plurality of all-distances sketches of the first node and the plurality of all-distances sketches of the second node by the computing device;
- and
- providing the estimated similarity in response to the indication of the first node and the indication of the second node by the computing device.
2 more elements
A method comprising:
- receiving a graph by a computing device, wherein the graph comprises a plurality of nodes and a plurality of edges, and each edge comprises a weight;
- generating a plurality of adjusted graphs from the graph by the computing device by, for each adjusted graph, adjusting the weights of the edges of the graph to generate the adjusted graph, wherein each adjusted graph has the same nodes as the graph;
- for each node of the graph, generating an all-distances sketch for the node by the computing device, wherein an all-distances sketch for a node comprises a subset of the plurality of nodes and a shortest distance between the associated node and each node of the subset of the plurality of nodes;
- for each adjusted graph:
- for each node of the adjusted graph, generating an all-distances sketch for the node by the computing device;
- and
- for each node, associating the node with the all-distances sketches generated for the node from the graph and each of the adjusted graphs by the computing device.
4 more elements
A system comprising:
- at least one computing device;
- a similarity engine adapted to:
- receive a graph, wherein the graph comprises a plurality of nodes and a plurality of edges;
- for each node of the graph, generate an all-distances sketch for the node, wherein an all-distances sketch of a node comprises a subset of the plurality of nodes and a distance between the associated node and each node of the subset of the plurality of nodes;
- receive an indication of a first node and an indication of a second node, wherein the first node and the second node are within the plurality of nodes of the graph;
- and
- estimate the similarity of the first node and the second node using the all-distances sketch of the first node and the all-distances sketch of the second node.
4 more elements
Dependencies are inferred from the claim text.