摘要: Abstract Since the first investigations on web-graph compression, it has been clear that ordering of nodes a web graph fundamental influence compression rate (usually expressed as number bits per link). The authors LINK database [Randall et al. 02], for instance, investigated three different approaches: an extrinsic (URL ordering) and two intrinsic orderings based rows adjacency matrix (lexicographic Gray code); they concluded URL many advantages in spite small penalty compression. In this paper we approach issue more systematic way, testing some known proposing new ones. Our experiments are made WebGraph framework [Boldi Vigna 04], show technique structure can produce significantly results. particular, transposed graph, is less effective, mixed orderi...
sci-hub.se 参考文章(31)
Masaru Kitsuregawa, Yasuhito Asano, Masashi Toyoda, Hiroshi Imai, Tsuyoshi Ito, Compact Encoding of the Web Graph Exploiting Various Power Laws: Statistical Reason Behind Link Database. web-age information management. pp. 37- 46 ,(2003)
Donald E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations (Art of Computer Programming) The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations (Art of Computer Programming). ,(2005)
Paolo Boldi, Massimo Santini, Sebastiano Vigna, Permuting Web Graphs workshop on algorithms and models for the web graph. pp. 116- 126 ,(2009) , 10.1007/978-3-540-95995-3_10
Fabrizio Silvestri, Sorting out the document identifier assignment problem european conference on information retrieval. pp. 101- 112 ,(2007) , 10.1007/978-3-540-71496-5_12
Jean-Loup Guillaume, Matthieu Latapy, Laurent Viennot, Efficient and Simple Encodings for the Web Graph Advances in Web-Age Information Management. ,vol. 2419, pp. 328- 337 ,(2002) , 10.1007/3-540-45703-8_30
Nieves R. Brisaboa, Susana Ladra, Gonzalo Navarro, k2-Trees for Compact Web Graph Representation string processing and information retrieval. ,vol. 5721, pp. 18- 30 ,(2009) , 10.1007/978-3-642-03784-9_3
D. Blandford, G. Blelloch, Index compression through document reordering data compression conference. pp. 342- 351 ,(2002) , 10.1109/DCC.2002.999972
Yasuhito Asano, Yuya Miyawaki, Takao Nishizeki, Efficient Compression of Web Graphs Lecture Notes in Computer Science. pp. 1- 11 ,(2008) , 10.1007/978-3-540-69733-6_1
György Turán, On the succinct representation of graphs Discrete Applied Mathematics. ,vol. 8, pp. 289- 294 ,(1984) , 10.1016/0166-218X(84)90126-4
N.J. Larsson, A. Moffat, Offline dictionary-based compression data compression conference. pp. 296- 305 ,(1999) , 10.1109/DCC.1999.755679