Patent ID: 8903824
Filing Date: 2014-12-02
Classification: G06F

Abstract:
1. A method for processing a random-walk based vertex-proximity query on a graph, wherein the method comprises: dividing a graph of vertices into multiple clusters that are each estimated to contain a random walk for a duration of time, wherein said dividing comprises dividing the graph of vertices into multiple clusters based on a conductance value computed for each of the multiple clusters, and wherein the conductance value for each of the multiple clusters is defined as wherein d v denotes the degree of vertex v and ∂(s) denotes the set of edges with exactly one end-point in cluster S; computing meta-information for each of the multiple clusters, wherein the meta-information is related to the random walk inside each of the multiple clusters from the graph; dynamically updating the multiple clusters and corresponding meta-information upon modification of the graph; identifying a subset of one or more clusters from the multiple updated clusters that are relevant to a query vertex; and processing a nearest-neighbor query on the subset of one or more identified clusters by: wherein at least one of the steps is carried out by a computer device.