Patent Document ID: 8090729
Application ID: 12396514
Patent Flag: 1

Claim One:
1. A method for efficiently computing a pairwise distance between nodes in a large graph, at least some of the nodes comprising one or more web-pages, the method comprising: generating a URL-sketch of respective web-pages in an index of web-pages, comprising: extracting labels from the respective web-pages; and storing sets of labels for respective web-pages in the index for efficient storage and retrieval; generating a neighborhood-sketch for the respective web-pages in the index using URL-sketches, comprising: determining a neighborhood for a web-page comprising neighboring nodes based at least in part upon a URL-sketch for the web-page; and generating a neighborhood sketch for the web-page using labels associated with the respective neighboring nodes; and determining a distance between two nodes in the index, comprising: computing an approximate number of paths between the two nodes, using neighborhood sketches of the two nodes; and computing an approximate path length between the two nodes, using the neighborhood sketches of the two nodes.