{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,23]],"date-time":"2025-12-23T10:29:41Z","timestamp":1766485781777,"version":"build-2065373602"},"reference-count":20,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2009,8,25]],"date-time":"2009-08-25T00:00:00Z","timestamp":1251158400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The Web Graph is a large-scale graph that does not fit in main memory, so that lossless compression methods have been proposed for it. This paper introduces a compression scheme that combines efficient storage with fast retrieval for the information in a node. The scheme exploits the properties of the Web Graph without assuming an ordering of the URLs, so that it may be applied to more general graphs. Tests on some datasets of use achieve space savings of about 10% over existing methods.<\/jats:p>","DOI":"10.3390\/a2031031","type":"journal-article","created":{"date-parts":[[2009,8,25]],"date-time":"2009-08-25T10:20:51Z","timestamp":1251195651000},"page":"1031-1044","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":98,"title":["Graph Compression by BFS"],"prefix":"10.3390","volume":"2","author":[{"given":"Alberto","family":"Apostolico","sequence":"first","affiliation":[{"name":"College of Computing, Georgia Institute of Technology, 801 Atlantic Drive, Atlanta, GA 30332, USA"},{"name":"Dipartimento di Ingegneria dell\u2019Informazione, Universit\u00e0 di Padova, Via Gradenigo 6\/A, I-35131 Padova, Italy"}]},{"given":"Guido","family":"Drovandi","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica e Automazione, Universit\u00e0 di Roma Tre, Via della Vasca Navale 79, I-00146 Roma, Italy"},{"name":"Istituto di Analisi dei Sistemi ed Informatica (IASI), CNR, Viale Manzoni 30, I-00185 Roma, Italy"}]}],"member":"1968","published-online":{"date-parts":[[2009,8,25]]},"reference":[{"key":"ref_1","unstructured":"Adler, M., and Mitzenmacher, M. (2001, January March). Towards compressing web graphs. Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, USA."},{"key":"ref_2","unstructured":"Asano, Y., Miyawaki, Y., and Nishizeki, T. (-, January June). Efficient compression of web graphs. Proceedings of the 14th annual international conference on Computing and Combinatorics, Dalian, China."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Boldi, P., and Vigna, S. (,  2004). The web graph framework I: Compression techniques. Proceedings of the Thirteenth International World Wide Web Conference, New York, NY, USA.","DOI":"10.1145\/988672.988752"},{"key":"ref_4","unstructured":"Claude, F., and Navarro, G. (2007, January October). A fast and compact web graph representation. Proceedings of 14th International Symposium on String Processing and Information Retrieval, Santiago, Chile."},{"key":"ref_5","unstructured":"Randall, K.H., Stata, R., Wiener, J.L., and Wickremesinghe, R.G. (2002, January April). The link database: fast access to graphs of the web. Proceedings of the Data Compression Conference (DCC \u201902), Snowbird, UT, USA."},{"key":"ref_6","unstructured":"Suel, T., and Yuan, J. (2001, January March). Compressing the graph structure of the web. Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, USA."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Buehrer, G., and Chellapilla, K. (2008, January February). A scalable pattern mining approach to web graph compression with communities. Proceedings of the international conference on Web search and web data mining, Palo Alto, CA, USA.","DOI":"10.1145\/1341531.1341547"},{"key":"ref_8","first-page":"711","article-title":"UbiCrawler: a scalable fully distributed web crawler","volume":"34","author":"Boldi","year":"2004","journal-title":"Software: Pract. Exp."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/0166-218X(84)90126-4","article-title":"On the succinct representation of graphs","volume":"8","author":"Turan","year":"1984","journal-title":"Discrete Appl. Math."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1006\/jcss.1995.1065","article-title":"Clique partitions, graph compression and speeding-up algorithms","volume":"51","author":"Feder","year":"1995","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1080\/15427951.2005.10129113","article-title":"Codes for the world wide web","volume":"2","author":"Boldi","year":"2005","journal-title":"Internet Math."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1722","DOI":"10.1109\/5.892708","article-title":"Offline dictionary-based compression","volume":"88","author":"Larsson","year":"2000","journal-title":"IEEE"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Karande, C., Chellapilla, K., and Andersen, R. (2009, January February). Speeding up algorithms on compressed web graphs. Proceedings of the Second ACM International Conference on Web Search and Data Mining, Barcelona, Spain.","DOI":"10.1145\/1498759.1498836"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0169-7552(98)00110-X","article-title":"The anatomy of a large-scale hypertextual web search engine","volume":"30","author":"Brin","year":"1998","journal-title":"Comput. Netw. ISDN Syst."},{"key":"ref_15","unstructured":"Page, L., Brin, S., Motwani, R., and Winograd, T. (1999). The pagerank citation ranking: bringing order to the web, Stanford InfoLab. Previous number = SIDL-WP-1999-0120."},{"key":"ref_16","unstructured":"Chierichetti, F., Kumar, R., Lattanzi, S., Mitzenmacher, M., Panconesi, A., and Raghavan, P. (1999, January August). On compressing social networks. Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, San Diego, CA, USA."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1109\/TIT.1975.1055349","article-title":"Universal codeword sets and representations of the integers","volume":"21","author":"Elias","year":"1975","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1145\/321812.321820","article-title":"Efficient storage and retrieval by content and address of static files","volume":"21","author":"Elias","year":"1974","journal-title":"J. ACM"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Fano, R.M. (1971). Project MAC. Computer Structures Group Memorandum 61. On the number of bits required to implement an associative memory, Massachusetts Institute of Technology.","DOI":"10.1080\/00029238.1971.11080829"},{"key":"ref_20","unstructured":"Lewis, J., and Neumann, U. (2003). Performance of java versus C++, Computer Graphics and Immersive Technology Lab, University of Southern California."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/2\/3\/1031\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T22:11:00Z","timestamp":1760220660000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/2\/3\/1031"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8,25]]},"references-count":20,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2009,9]]}},"alternative-id":["a2031031"],"URL":"https:\/\/doi.org\/10.3390\/a2031031","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2009,8,25]]}}}