LARGE GRAPH MEASUREMENT

• US 20100228731A1
• Filed: 03/03/2009
• Published: 09/09/2010
• Est. Priority Date: 03/03/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Gollapudi, Sreenivas
• Granted Patent: US 8,090,729 B2
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]

Abstract

As provided herein, a pairwise distance between nodes in a large graph can be determined efficiently. URL-sketches are generated for respective nodes in an index by extracting labels from respective nodes, which provide a reference to a link between the nodes, aggregating the labels into sets for respective nodes, and storing the sets of labels as URL-sketches. Neighborhood-sketches are generated for the respective nodes in the index using the URL-sketches, by determining a neighborhood for a node and generating a sketch using labels that are associated with the respective neighboring nodes. A distance between two nodes is determined by computing an approximate number of paths and an approximate path length between the two nodes, using the neighborhood sketches for the two nodes.

Claims

1. A method for efficiently computing a pairwise distance between nodes in a large graph, 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 the URL-sketches, comprising;

determining a neighborhood for a web-page comprising neighboring nodes; 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 the neighborhood sketches of the two nodes; and

computing an approximate path length between the two nodes, using the neighborhood sketches of the two nodes.

2. The method of claim 1, extracting labels from the respective web-pages, comprising extracting a set of keywords.

3. The method of claim 2, extracting sets of keywords from the respective web-pages, comprising

identifying proxy-strings in a first web-page that reference a link to a second web-page;

and

associating a set of proxy-strings from the web-pages in the index to the second web-page.

4. The method of claim 1, storing sets of keywords for respective web-pages for efficient storage and retrieval, comprising mapping the set of keywords for a web-page into a bit-vector.

5. The method of claim 4, mapping the set of keywords for a web-page into a bit-vector comprising mapping the set of keywords for a web-page into a bit-vector in hamming space.

6. The method of claim 1, generating a URL-sketch comprising storing the URL-sketch for respective web-pages in a hash table.

7. The method of claim 1, generating a URL-sketch of respective web-pages in an index of web-pages, comprising using minimal hashing of a web-page'"'"'s content to compute a sketch of the web-page.

8. The method of claim 1, determining a neighborhood for a web-page comprising one of:

computing neighboring nodes using a random-surfer model starting from the web-page;

computing neighboring nodes using a node similarity bias walk model starting from the web-page; and

computing neighboring nodes using a breadth-first type graph exploration starting from the web-page.

9. The method of claim 1, generating a neighborhood sketch for the web-page using labels associated with the respective neighboring nodes comprising:

identifying a set of labels that are common to the respective nodes in the neighborhood; and

storing sets of labels for respective nodes for efficient storage and retrieval.

10. The method of claim 1, determining an approximate number of paths between the two nodes, comprising computing a number of common nodes between the neighborhood-sketches of the two nodes.

11. The method of claim 1, determining a path length between the neighborhood-sketches for the two nodes comprising:

comparing corresponding distance reference neighborhood sketches from the two nodes that represent nodes of known path lengths; and

determining how many paths connect the two nodes at the respective reference distances.

12. The method of claim 1, determining a distance between the two nodes, comprising:

computing an effective resistance between the two nodes using a hamming distance between the two nodes.

13. A system for efficiently computing a pairwise distance between nodes in a large graph, comprising:

a URL-sketch generator configured to create URL-sketches of web-pages in an index of web-pages, comprising;

a web-page label extractor configured to extract a set of labels that reference a first web-page from a set of second web-pages in an index for respective web-pages in the index; and

a label set store configured to store sets of labels for respective web-pages in for efficient storage and retrieval;

a neighborhood generator configured to generate a neighborhood-sketch for the respective web-pages in the index, comprising;

a neighborhood determiner configured to compute a neighborhood for a web-page comprising neighboring nodes, using the URL-sketches; and

a neighborhood sketcher configured to generate a neighborhood sketch for the web-page using labels associated with the respective neighboring nodes; and

a node distance measuring component configured to determining a distance between two nodes in the index.

14. The system of claim 13, the web-page label extractor comprising:

a keyword identifier configured to identify proxy-strings in a first web-page that reference a link to a second web-page; and

a keyword associating component configured to associate a set of proxy-strings from the web-pages in the index to the second web-page.

15. The system of claim 13, the label set store comprising a hash-table type storage component.

16. The system of claim 13, the neighborhood determiner comprising one of:

a random surfer modeling component configured to compute neighboring nodes for a web-page by randomly crawling a URL-sketch for the web-page starting from the web-page;

a similarity bias walking component configured to compute neighboring nodes for a web-page by crawling a URL-sketch for the web-page using a node similarity bias starting from the web-page; and

a breadth-first type graph explorer model configured to use a deterministic crawl of a URL-sketch for the web-page starting from the web-page.

17. The system of claim 13, the neighborhood sketcher comprising:

a neighborhood label identifier configured to identify a set of labels that are common to the respective nodes in the neighborhood; and

a label set store configured to store sets of labels for respective nodes for efficient storage and retrieval.

18. The system of claim 13, the node distance measuring component comprising one of:

an effective resistance determiner configured to compute an effective resistance between the two nodes using a hamming distance between the two nodes; and

a path determiner configured to compute an approximate path length and an approximate number of paths between the two nodes.

19. The system of claim 18, the path determiner comprising:

a path number determiner configured to determine an approximate number of paths between the two nodes; and

a path length determiner configured to determine a path length between the neighborhood-sketches of the two nodes for the approximate number of paths between the two nodes.

20. A method for efficiently computing a pairwise distance between nodes in a large graph, comprising:

generating a URL-sketch of respective web-pages in an index of web-pages, comprising;

extracting sets of keywords from the respective web-pages, comprising

identifying proxy-strings in a first web-page that reference a link to a second web-page; and

associating a set of proxy-strings from the web-pages in the index to the second web-page; and

storing sets of keywords for respective web-pages for efficient storage and retrieval, comprising;

mapping the set of keywords for a web-page into a bit-vector in hamming space; and

storing the URL-sketch for respective web-pages in a hash table;

generating a neighborhood-sketch for the respective web-pages in the index using the URL-sketches, comprising;

determining a neighborhood for a web-page comprising one of;

computing neighboring nodes using a random-surfer model starting from the web-page;

computing neighboring nodes using a node similarity bias walk starting from the web-page; and

computing neighboring nodes using a breadth-first type graph exploration starting from the web-page;

generating a neighborhood sketch for the web-page using labels associated with the respective neighboring nodes, comprising;

identifying a set of labels that are common to the respective nodes in the neighborhood; and

storing sets of labels for respective nodes for efficient storage and retrieval; and

determining a distance between two nodes in the index, comprising one of;

computing an effective resistance between the two nodes using a hamming distance between the two nodes; and

computing an approximate path length between the two nodes, comprising;

determining an approximate number of paths between the two nodes; and

determining a path length between the neighborhood-sketches for the two nodes using the approximate number of paths between the two nodes.