The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Mar. 04, 2014
Filed:
Feb. 15, 2010
Marc A. Najork, Palo Alto, CA (US);
Sreenivas Gollapudi, Cupertino, CA (US);
Rina Panigrahy, Sunnyvale, CA (US);
Atish Das Sarma, Atlanta, GA (US);
Marc A. Najork, Palo Alto, CA (US);
Sreenivas Gollapudi, Cupertino, CA (US);
Rina Panigrahy, Sunnyvale, CA (US);
Atish Das Sarma, Atlanta, GA (US);
Microsoft Corporation, Redmond, WA (US);
Abstract
Sketches are generated for each node in a graph. For undirected graphs, each sketch for a node may include an indicator of a node from a seed set of nodes and the shortest distance between the node and the indicated node. When a request is received for the shortest distance between two nodes of the graph, the sketches for each of the two nodes are retrieved, and nodes that are indicated in both of the sketches are determined. The distances between each of the two nodes and a determined node as indicated in the sketches is summed for each of the determined nodes, and the sum having the least distance is selected as the estimated shortest distance between the two nodes.