Web graph compression through scalable pattern mining

• US 7,818,303 B2
• Filed: 01/29/2008
• Issued: 10/19/2010
• Est. Priority Date: 01/29/2008
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Buehrer, Gregory T., Chellapilla, Kumar Hemachandra
• Primary Examiner(s): EHICHIOYA, IRETE FRED
• Application Number:
  US12/022,136
• Publication Number:
  US 20090193044A1
• Time in Patent Office: 994 Days
• Field of Search: 707/693, 707/790, 707/802, 707/999.101, 715/205, 715/242
• US Class Current: 707/693
• CPC Class Codes: G06F 16/95 Retrieval from the web

Abstract

A method and a processing device are provided for compressing a web graph including multiple nodes and links between the multiple nodes. Nodes of the web graph may be clustered into groups including no more than a predetermined number of nodes. A list of links of the clustered nodes may be created and sorted based on a frequency of occurrence of each of the links. A prefix tree may be created based on the sorted list of links. The prefix tree may be walked to find candidate virtual nodes. The candidate virtual nodes may be analyzed according to a selection criteria and a virtual node may be selected. The prefix tree may be adjusted to account for the selection of the virtual node and the virtual node may be added to the web graph.

Claims

1. A machine-implemented method for compressing a graph including a plurality of nodes and a plurality of links between ones of the plurality of nodes, the machine-implemented method comprising:

clustering similar nodes of the plurality nodes;

scanning a node list, corresponding to the clustered similar nodes of the plurality of nodes to determine frequencies of occurrence of links of the clustered similar nodes;

sorting a list of the links of the clustered similar nodes based on the determined frequencies of occurrence of the links of the clustered similar nodes to produce a sorted link list;

adding each of the links, having a frequency of occurrence greater than a predetermined number, from the sorted link list as an item of a prefix tree, along with an associated node list;

walking the prefix tree to produce a list of candidate virtual nodes;

determining a respective compression performance for each pattern corresponding to a respective candidate virtual node according to a compression performance formula Compression(P)=(P.frequency−

1)(P.size−

1)−

1, where Compression(P) is compression performance for a pattern P, P.frequency is a number of the clustered similar nodes having links corresponding to the pattern P, and P.size is a length of the pattern P in the prefix tree;

sorting the list of candidate virtual nodes based on results of applying the compression performance formula;

selecting one of the list of candidate virtual nodes as a virtual node based on one of the patterns having a highest determined compression performance;

creating the virtual node; and

substituting links to the virtual node for links corresponding to the one of the patterns, wherein

the machine-implemented method is implemented either on one processing device or on a networked plurality of processing devices.

2. The machine-implemented method of claim 1, wherein the clustering of similar nodes of the plurality of nodes further comprises:

determining k hash values with respect to each of the plurality of nodes to produce a n×

k matrix, where n is a number of the nodes in the graph,

sorting the n×

k matrix lexicographically to produce a sorted n×

k matrix, and

forming a list of ones of the plurality nodes having a size less than a predetermined number based on ones of the sorted n×

k matrix having a corresponding same hash value.

3. The machine-implemented method of claim 2, wherein the hash values are minhash values.

4. The machine-implemented method of claim 1, wherein the walking of the prefix tree to produce a list of candidate virtual nodes further comprises:

walking the prefix tree to find a leaf of the prefix tree,

adding a candidate virtual node to the list of candidate virtual nodes based on the found leaf of the prefix tree when an associated node list has at least two nodes,

walking up the prefix tree from the leaf to attempt to find an ancestor item having an associated node list length greater than a length of the associated node list of the found leaf, and

adding a second candidate virtual node to the list of candidate virtual nodes based on the found ancestor item when the found ancestor item has the associated node list length greater than the associated node list length of the found leaf.

5. The machine-implemented method of claim 1, further comprising:

parallelizing the machine-implemented method by;

providing information with respect to groups of the clustered similar nodes to different processing devices of the networked plurality of processing devices, wherein;

each of the different processing devices performs, with respect to a group of the clustered similar nodes;

scanning a node list, corresponding to the group of clustered similar nodes of the plurality of nodes to determine frequencies of occurrence of links of the group of clustered similar nodes;

sorting a list of the links of the group of the clustered similar nodes based on the determined frequencies of occurrence of the links of the group of the clustered similar nodes to produce a sorted link list with respect to the group of the clustered similar nodes;

adding each of the links of the group of the clustered similar nodes, having a frequency of occurrence greater than a predetermined number, from the sorted link list with respect to the group of the clustered similar nodes as an item of a prefix tree, along with an associated node list;

walking the prefix tree to produce a list of candidate virtual nodes;

determining a respective compression performance for each pattern corresponding to a respective candidate virtual node according to the compression performance formula;

sorting the list of candidate virtual nodes based on results of applying the compression performance formula; and

selecting one of the list of candidate virtual nodes as a virtual node based on one of the patterns having a highest determined compression performance.

6. A processing device comprising:

at least one processor; and

a memory connected to the at least one processor, the memory further comprising;

instructions for determining similar nodes of a graph and clustering the similar nodes, each of the nodes representing a respective network document and each link of a respective node being a link to a second respective node,

instructions for finding a plurality of patterns among the clustered similar nodes, the instructions for finding a plurality of patterns among the clustered similar nodes further comprising;

instructions for creating a histogram of frequencies of occurrence of links of the clustered similar nodes, and

instructions for adding a plurality of items to a prefix tree based on a descending frequency of occurrence order of the links of the clustered similar nodes, each of the plurality of items including a respective link ID and respective node IDs of associated ones of the clustered similar nodes, each link corresponding to the respective link ID having at least a predetermined frequency of occurrence,

instructions for walking ones of the plurality of items of the prefix tree from a root item to find a next unprocessed item having a longest path and more than one associated node,

instructions for adding a next candidate virtual node to a list of candidate virtual nodes based on the found next unprocessed item having the longest path and the more than one associated node ID,

instructions for marking the next found unprocessed item to indicate processing of the item,

instructions for walking up the prefix tree to find a new next unprocessed item having a larger number of associated nodes than the next found item, and

instructions for adding a new next candidate virtual node to a list of candidate virtual nodes based on the found new next unprocessed item having the larger number of associated nodes; and

the memory further comprising;

instructions for selecting one of the found plurality of patterns and creating a virtual node, the instructions for selecting one of the found plurality of patterns and creating a virtual node further comprising;

instructions for determining a compression performance with respect to each one of the list of candidate virtual nodes according to a compression performance formula Compression(P)=(P.frequency−

1)(P.size−

1)−

1, where Compression(P) is compression performance for a pattern P, P.frequency is a number of the clustered similar nodes having links corresponding to the pattern P, and P.size is a length of the pattern P in the prefix tree,

instructions for selecting one of the list of candidate virtual nodes having a highest compression performance, and

instructions for creating the virtual node based on the selected one of the list of candidate virtual nodes; and

instructions for replacing links corresponding to the selected virtual node with links to the virtual node.

7. The processing device of claim 6, wherein the instructions for determining similar nodes of a graph and clustering the similar nodes further comprise:

instructions for hashing each link of each respective node using k perfect hash functions to produce a set of k hash values for each of the links of each of the respective nodes,

instructions for determining, from among corresponding ones of the set of k hash values for each of the links of each of the respective nodes, k respective minhash values for each of the respective nodes,

instructions for adding the respective k minhash values to a n×

k matrix, where n is a number of nodes represented in the n×

k matrix,

instructions for lexicographically sorting the n×

k matrix to produce a sorted n×

k matrix, and

instructions for forming a list of ones of the plurality nodes having a list size less than a predetermined number based on ones of the sorted n×

k matrix having a same minimum hash value with respect to at least one corresponding k minhash value.

8. The processing device of claim 6, wherein the memory further comprises:

instructions for removing an item corresponding to the virtual node from the prefix tree, and

instructions for adjusting the associated nodes of the items of the prefix list to remove any nodes corresponding to the associated nodes of an item corresponding to the virtual node.

9. The processing device of claim 6, wherein the instructions for replacing links corresponding to the virtual node with links to the virtual node further comprises:

instructions for replacing links of nodes of a graph, corresponding to one of a plurality of nodes of a node list associated with the virtual node and further corresponding to a link of the one of the found plurality of patterns, with a link to the virtual node.

10. A system comprising:

a plurality of processing devices networked together, each of the processing devices comprising;

at least one processor; and

a memory connected to the at least one processor, the memory of a first one of the processing devices comprising;

instructions for determining groups of similar nodes of a graph and clustering the groups of similar nodes,

instructions for providing respective groups of the groups of similar nodes to respective second ones of the plurality of processing devices,

instructions for receiving respective virtual nodes from each of the second ones of the plurality of processing devices, and

instructions for replacing links corresponding to the virtual nodes with links to the virtual nodes; and

the memories of each of the second ones of the plurality of processing devices further comprising;

instructions for creating a histogram of frequencies of occurrence of links of similar nodes of the respective group of the groups of similar nodes,

instructions for adding a plurality of items to a prefix tree based on a descending frequency of occurrence order of the links of the similar nodes of the respective group of the groups of similar nodes, each of the plurality of items including a respective link ID and respective node IDs of corresponding ones of the similar nodes, each link corresponding to the respective link ID having least a predetermined frequency of occurrence,

instructions for walking ones of the plurality of items of the prefix tree from a root item to find a next unprocessed item having a longest path and more than one respective node ID,

instructions for adding a next candidate virtual node to a list of candidate virtual nodes based on the found next unprocessed item having the longest path and more than one respective node ID,

instructions for marking the next found unprocessed item to indicate processing of the item,

instructions for walking up the prefix tree to find a new next unprocessed item having a larger number of node IDs than the next found item,

instructions for adding a new next candidate virtual node to a list of candidate virtual nodes based on the found new next unprocessed item having a larger number of node IDs than the next found item,

instructions for calculating a compression performance of respective ones of the items of the candidate virtual nodes according to;

Compression(P)=(P.frequency−

1)(P.size−

1)−

1, where Compression(P) is compression performance for a pattern P, P.frequency is a number of the similar nodes of the respective group having links corresponding to the pattern P, and P.size is a length of the pattern P in the prefix tree,

instructions for selecting one item from the list of candidate virtual nodes having a highest compression performance, and

instructions for providing, to the first one of the processing devices as a virtual node, the selected one item from the list of candidate virtual nodes.

11. The system of claim 10, wherein the instructions for determining groups of similar nodes of a graph and clustering the groups of similar nodes further comprise:

instructions for hashing each link of each respective node using k perfect hash functions to produce a set of k hash values for each of the links of each of the respective nodes,

instructions for determining, from among corresponding ones of the set of k hash values for each of the links of each of the respective nodes, respective k minhash values,

instructions for adding each of the respective k minhash values to a n×

k matrix, where n is a number of nodes represented in the n×

k matrix,

instructions for lexicographically sorting the n×

k matrix to produce a sorted n×

k matrix, and

instructions for forming a list of ones of the plurality nodes having a list size less than a predetermined number based on ones of the sorted n×

k matrix having a same minhash value with respect to at least one corresponding k minhash value.

12. The system of claim 10, wherein the memories of the second ones of the processing devices further comprise:

instructions for removing an item corresponding to the virtual node from the prefix tree, and

instructions for adjusting the node lists of the items of the prefix list to remove any nodes corresponding to the node list of the item corresponding to the virtual node.

13. The system of claim 10, wherein:

each of a plurality of nodes of the graph represent a respective network document, and

each of the plurality of nodes includes at least one link, each of the at least one link representing a hyperlink from a corresponding network document to another network document.