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:
May. 03, 2016
Filed:
Oct. 12, 2012
Microsoft Corporation, Redmond, WA (US);
Rina Panigrahy, San Ramon, CA (US);
Mikhail Kapralov, Stanford, CA (US);
Microsoft Technology Licensing, LLC, Redmond, WA (US);
Abstract
A sparsifier is generated from a union of multiple spanners of a graph. The edges of the sparsifier are weighted based on a measure of connectivity called robust connectivity. The robust connectivity of a node pair is the highest edge sampling probability at which a distance between the pair is likely to drop below a specified length. Each spanner is generated from a subgraph of the graph that is generated using a decreasing sampling probability. For the weight of each edge, a spanner is determined where an estimated distance between the nodes associated with the edge is greater than a threshold distance. The sampling probability of the subgraph used to generate the spanner is an estimate of the robust connectivity of the edge. The weight of the edge is set to the inverse of the estimated robust connectivity.