Web graph compression through scalable pattern mining

Details Web graph compression through scalable pattern mining Web graph compression through scalable pattern mining

2011-03-22

2011-03-22

Ehichioya, Fred I (Department: 2156)

Data processing: database and file management or data structures

Data integrity

Fragmentation, compaction and compression

C707S790000, C707S802000, C715S205000

Reexamination Certificate

active

07912818

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.

REFERENCES:
patent: 6073135 (2000-06-01), Broder et al.
patent: 6138113 (2000-10-01), Dean et al.
patent: 6556983 (2003-04-01), Altschuler et al.
patent: 6886129 (2005-04-01), Raghavan et al.
patent: 6920477 (2005-07-01), Mitzenmacher
patent: 7089252 (2006-08-01), Tomlin et al.
patent: 2004/0210826 (2004-10-01), Najork
patent: 2006/0026191 (2006-02-01), McSherry
patent: 2007/0168533 (2007-07-01), Canright
patent: 2007/0220064 (2007-09-01), Najork
Boldi, et al., “The WebGraph Framework I: Compression Techniques”, WWW'2004, May 17-22, 2004, ACM, pp. 595-602.
Mahdian et al., “Pre-Compression Algorithm for Link Structure of the Web”, 1 Ith CSI Computer Conference (CSICC'2006), School of Computer Science, IPM, Jan. 24-26, 2006, pp. 1-5.
Claude, et al., “A Fast and Compact Web Graph Representation”, 2007, pp. 118-129.
Boldi, et al., “The WebGraph Framework I: Compression Techniques”, WWW'2004, May 17-22, 2004, ACM, pp. 595-602.
Mahdian, et al., “Pre-Compression Algorithm for Link Structure of the Web”, 1 Ith CSI Computer Conference (CSICC'2006), School of Compter Science, IPM, Jan. 24-26, 2006, pp. 5.
Claude, et al., “A Fast and Compact Web Graph Representation”, vol. 4726, 2007, pp. 11.
“WebGraph”, retrieved at <<http://webgraph.dsi.unimi.it/>>, pp. 3.

Affiliated with

Also associated with

Rating

Web graph compression through scalable pattern mining does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Web graph compression through scalable pattern mining, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Web graph compression through scalable pattern mining will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2760279