Web graph compression through scalable pattern mining

• US 7,912,818 B2
• Filed: 09/13/2010
• Issued: 03/22/2011
• 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; Fred I
• Application Number:
  US12/880,747
• Publication Number:
  US 20100332476A1
• Time in Patent Office: 190 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;

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 a 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 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;

producing a sorted link list of the clustered similar nodes based on frequencies of occurrence of links of the clustered similar nodes;

adding each of the links from the sorted link list as an item of a prefix tree, along with an associated node list;

producing a list of candidate virtual nodes based on the prefix tree;

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;

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; 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.

7. The machine-implemented method of claim 6, 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.

8. The machine-implemented method of claim 7, wherein the hash values are minhash values.

9. The machine-implemented method of claim 6 further comprising:

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

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

10. A processing device comprising:

at least one processor; and

a memory connected to the at least one processor, the memory including instructions for performing a method comprising;

clustering groups of similar nodes of a graph;

producing a sorted link list of the clustered similar nodes based on frequencies of occurrence of links of the clustered similar nodes;

adding each of the links from the sorted link list as an item of a prefix tree, along with an associated node list;

producing a list of candidate virtual nodes based on the prefix tree;

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;

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; and

substituting links to the virtual node for links corresponding to the one of the patterns.

11. The system of claim 10, wherein the method further comprises:

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.