Patent ID: 9690827
Date: 2017-06-27
CPC Classifications: G06F

Claim:
1. A method comprising: receiving a graph by a computing device, wherein the graph comprises a plurality of nodes; for each node of the graph, receiving an all-distances sketch by the computing device, wherein an all-distances sketch associated with 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; for each node of the graph, determining a historic inverse probability (HIP) estimator for the node using the all-distances sketch associated with the node by scanning the entries from the all-distances sketch in order of increasing distance from the node, and for each entry scanned, determining an adjusted weight, by the computing device, wherein the HIP estimator includes the adjusted weights for every entry scanned for the node; receiving a request to perform one or more graph operations on the graph; and performing the one or more graph operations on the graph using one or more of the HIP estimators associated with the nodes by the computing device.