摘要: We consider the problem of compressing graphs link structure World Wide Web. provide efficient algorithms for such compression that are motivated by random graph models describing The based on reducing to finding a minimum spanning free in directed related original graph. performance generated suggests taking advantage Web, one may achieve significantly better than natural Huffman-based schemes. also hardness results demonstrating limitations extensions our approach.
harvard.edu
du.edu 
sci-hub.se 参考文章(20)
Timothy C. Bell, Alistair Moffat, Ian H. Witten, Managing gigabytes 2nd edition ,(1999)
Chandra Chekuri, Moses Charikar, Ashish Goel, Sudipto Guha, To-yat Cheung, Ming Li, Zuo Dai, Approximation algorithms for directed Steiner problems symposium on discrete algorithms. pp. 192- 200 ,(1998) , 10.5555/314613.314700
Krishna Bharat, Andrei Broder, Monika Henzinger, Puneet Kumar, Suresh Venkatasubramanian, The connectivity server: fast access to linkage information on the Web the web conference. ,vol. 30, pp. 469- 477 ,(1998) , 10.1016/S0169-7552(98)80047-0
Harold N. Gabow, Zvi Galil, Thomas Spencer, Robert E. Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs Combinatorica. ,vol. 6, pp. 109- 122 ,(1986) , 10.1007/BF02579168
R. E. Tarjan, Finding optimum branchings Networks. ,vol. 7, pp. 25- 35 ,(1977) , 10.1002/NET.3230070103
R. M. Karp, A simple derivation of edmonds' algorithm for optimum branchings Networks. ,vol. 1, pp. 265- 272 ,(1971) , 10.1002/NET.3230010305
Donald F. Caldwell, Kenneth W. Church, Adam L. Buchsbaum, Glenn S. Fowler, S. Muthukrishnan, Engineering the compression of massive tables: an experimental approach symposium on discrete algorithms. pp. 175- 184 ,(2000) , 10.5555/338219.338249
Sergey Brin, Lawrence Page, The anatomy of a large-scale hypertextual Web search engine the web conference. ,vol. 30, pp. 107- 117 ,(1998) , 10.1016/S0169-7552(98)00110-X
P. M. Camerini, L. Fratta, F. Maffioli, A note on finding optimum branchings Networks. ,vol. 9, pp. 309- 312 ,(1979) , 10.1002/NET.3230090403
William Aiello, Fan Chung, Linyuan Lu, A random graph model for massive graphs symposium on the theory of computing. pp. 171- 180 ,(2000) , 10.1145/335305.335326