The DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index.
The webgraph framework I: compression techniques
Abstract
Studying web graphs is often difficult due to their large size. Recently,several proposals have been published about various techniques that allow tostore a web graph in memory in a limited space, exploiting the inner redundancies of the web. The WebGraph framework is a suite of codes, algorithms and tools that aims at making it easy to manipulate large web graphs. This papers presents the compression techniques used in WebGraph, which are centred around referentiation and intervalisation (which in turn are dual to each other). WebGraph can compress the WebBase graph (118 Mnodes, 1 Glinks)in as little as 3.08 bits per link, and its transposed version in as littleas 2.89 bits per link.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1999) · Cited by 12,854
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1999) · Journal of the ACM · doi:10.1145/324133.324140 · Cited by 8,959
UbiCrawler: a scalable fully distributed Web crawler
Boldi, P., Codenotti, B., Santini, M., & Vigna, S. (2004) · Software: Practice and Experience · doi:10.1002/spe.587 · Cited by 560
Self-citationTowards compressing Web graphs
Adler, M., & Mitzenmacher, M. (2002) · Proceedings DCC 2001. Data Compression Conference · doi:10.1109/dcc.2001.917151 · Cited by 223
The Connectivity Server: fast access to linkage information on the Web
Bharat, K., Broder, A., Henzinger, M., Kumar, P., & Venkatasubramanian, S. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)80047-0 · Cited by 188
WebBase: a repository of Web pages
Hirai, J., Raghavan, S., Garcia-Molina, H., & Paepcke, A. (2000) · Computer Networks · doi:10.1016/s1389-1286(00)00063-3 · Cited by 183
Raghavan, S., & García-Molina, H. (2004) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2003.1260809 · Cited by 180
The Link Database: fast access to graphs of the Web
Randall, K. H., Stata, R., Wickremesinghe, R. G., & Wiener, J. L. (2003) · DCC · doi:10.1109/dcc.2002.999950 · Cited by 146
Compressing the graph structure of the Web
Suel, T., & Yuan, J. (2002) · DCC · doi:10.1109/dcc.2001.917152 · Cited by 134
Cited by
PowerGraph: distributed graph-parallel computation on natural graphs
Gonzalez, J. E., Low, Y., Gu, H., Bickson, D., & Guestrin, C. (2012) · doi:10.5555/2387880.2387883 · Cited by 1,451
Langville, A., & Meyer, C. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129091 · Cited by 894
GraphChi: Large-Scale Graph Computation on Just a PC
Kyrola, A., Blelloch, G. E., & Guestrin, C. (2018) · Figshare · doi:10.1184/r1/6605999 · Cited by 868
Ligra: a lightweight graph processing framework for shared memory
Shun, J., & Blelloch, G. E. (2013) · Proceedings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programming · doi:10.1145/2442516.2442530 · Cited by 798
Boldi, P., Rosa, M., Santini, M., & Vigna, S. (2011) · Proceedings of the 20th international conference on World wide web · doi:10.1145/1963405.1963488 · Cited by 592
Self-citationBackstrom, L., Boldi, P., Rosa, M., Ugander, J., & Vigna, S. (2012) · Proceedings of the 4th Annual ACM Web Science Conference · doi:10.1145/2380718.2380723 · Cited by 567
Self-citationGPS: a graph processing system
Salihoglu, S., & Widom, J. (2013) · Proceedings of the 25th International Conference on Scientific and Statistical Database Management · doi:10.1145/2484838.2484843 · Cited by 510
A Survey on PageRank Computing
Berkhin, P. (2005) · Internet Mathematics · doi:10.1080/15427951.2005.10129098 · Cited by 474
Main-memory triangle computations for very large (sparse (power-law)) graphs
Latapy, M. (2008) · Theoretical Computer Science · doi:10.1016/j.tcs.2008.07.017 · Cited by 458
Efficient aggregation for graph summarization
Tian, Y., Hankins, R. A., & Patel, J. M. (2008) · Proceedings of the 2008 ACM SIGMOD international conference on Management of data · doi:10.1145/1376616.1376675 · Cited by 442
Fast exact shortest-path distance queries on large networks by pruned landmark labeling
Akiba, T., Iwata, Y., & Yoshida, Y. (2013) · Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2463676.2465315 · Cited by 400
From "think like a vertex" to "think like a graph"
Tian, Y., Balmin, A., Corsten, S. A., Tatikonda, S., & McPherson, J. (2013) · Proceedings of the VLDB Endowment · doi:10.14778/2732232.2732238 · Cited by 352
On compressing social networks
Chierichetti, F., Kumar, R., Lattanzi, S., Mitzenmacher, M., Panconesi, A., & Raghavan, P. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557049 · Cited by 349
Graph summarization with bounded error
Navlakha, S., Rastogi, R., & Shrivastava, N. (2008) · Proceedings of the 2008 ACM SIGMOD international conference on Management of data · doi:10.1145/1376616.1376661 · Cited by 347
Direction-optimizing Breadth-First Search
Beamer, S., Asanovic, K., & Patterson, D. (2012) · 2012 International Conference for High Performance Computing, Networking, Storage and Analysis · doi:10.1109/sc.2012.50 · Cited by 325
Efficient semi-streaming algorithms for local triangle counting in massive graphs
Becchetti, L., Boldi, P., Castillo, C., & Gionis, A. (2008) · Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1401890.1401898 · Cited by 319
Self-citationBinary RDF representation for publication and exchange (HDT)
Fernández, J. D., Martínez-Prieto, M. A., Gutiérrez, C., Polleres, A., & Arias, M. (2013) · Journal of Web Semantics · doi:10.1016/j.websem.2013.01.002 · Cited by 316
Know your neighbors: web spam detection using the web topology
Castillo, C., Donato, D., Gionis, A., Murdock, V., & Silvestri, F. (2007) · Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/1277741.1277814 · Cited by 310
Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and Experiments
Fogaras, D., Rácz, B., Csalogány, K., & Sarlós, T. (2005) · Internet Mathematics · doi:10.1080/15427951.2005.10129104 · Cited by 282
Graph Summarization Methods and Applications: A Survey
Liu, Y., Safavi, T., Dighe, A., & Koutra, D. (2019) · ACM Computing Surveys · doi:10.1145/3186727 · Cited by 274
Piccolo: building fast, distributed programs with partitioned tables
Power, R., & Li, J. (2010) · doi:10.5555/1924943.1924964 · Cited by 252
Mining query logs: turning search usage data into knowledge
Silvestri, F. (2009) · Foundations and Trends® in Information Retrieval · doi:10.1561/1500000013 · Cited by 194
“• URL-sorting : it is a very simple heuristics, which assign documents block-wise, after sorting them by their URL; this is the first time URL-sorting is used to perform document clustering; this simple technique, already used for other IR tasks [43, 177, 202], can offer a remarkable improvement over a random assignme…”
MethodTowards Scaling Fully Personalized PageRank
Fogaras, D., & Rácz, B. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30216-2_9 · Cited by 84
“The assumption is made, since even with the latest compression techniques [3] it does not seem plausible to store the entire web graph in main memory.”
BackgroundDistributed PageRank computation based on iterative aggregation-disaggregation methods
Zhu, Y., Ye, S., & Li, X. (2005) · Proceedings of the 14th ACM international conference on Information and knowledge management · doi:10.1145/1099554.1099705 · Cited by 65
Summarizing static and dynamic big graphs
Khan, A., Bhowmick, S. S., & Bonchi, F. (2017) · Proceedings of the VLDB Endowment · doi:10.14778/3137765.3137825 · Cited by 45
The Software Heritage Graph Dataset: Large-scale Analysis of Public Software Development History
Pietri, A., Spinellis, D., & Zacchiroli, S. (2020) · Proceedings of the 17th International Conference on Mining Software Repositories · doi:10.1145/3379597.3387510 · Cited by 19
Symmetry-Aware Knowledge Graph Compression for LLM Grounding via Symbolic Retrieval
Prakash, V., & Dontabhaktuni, J. (2026) · doi:10.2139/ssrn.6826298
Metadata
- Authors
- Boldi, P., & Vigna, S.
- Venue
- Proceedings of the 13th international conference on World Wide Web
- Publisher
- ACM
- Published
- 2004-05-17
- Pages
- 595-602
- OpenAlex
- W1994727615
- Cited by
- 1,201
- References
- 9
- FWCI
- 12.14
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.