Compact Encoding of the Web Graph Exploiting Various Power Distributions

Yasuhito ASANO  Tsuyoshi ITO  Hiroshi IMAI  Masashi TOYODA  Masaru KITSUREGAWA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E87-A   No.5   pp.1183-1184
Publication Date: 2004/05/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
Web graph,  encoding,  power distributions,  

Full Text: PDF>>
Buy this Article



Summary: 
Compact encodings of the web graph are required in order to keep the graph on the main memory and to perform operations on the graph efficiently. In this paper, we propose a new compact encoding of the web graph. It is 10% more compact than Link2 used in the Connectivity Server of Altavista and 20% more compact than the encoding proposed by Guillaume et al. in 2002 and is comparable to it in terms of extraction time.