The Link Database: fast access to graphs of the Web
The DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.
Abstract
The Connectivity Server is a special-purpose database whose schema models the Web as a graph: a set of nodes (URL) connected by directed edges (hyperlinks). The Link Database provides fast access to the hyperlinks. To support easy implementation of a wide range of graph algorithms we have found it important to fit the Link Database into RAM. In the first version of the Link Database, we achieved this fit by using machines with lots of memory (8 GB), and storing each hyperlink in 32 bits. However, this approach was limited to roughly 100 million Web pages. This paper presents techniques to compress the links to accommodate larger graphs. Our techniques combine well-known compression methods with methods that depend on the properties of the Web graph. The first compression technique takes advantage of the fact that most hyperlinks on most Web pages point to other pages on the same host as the page itself. The second technique takes advantage of the fact that many pages on the same host share hyperlinks, that is, they tend to point to a common set of pages. Together, these techniques reduce space requirements to under 6 bits per link. While (de)compression adds latency to the hyperlink access time, we can still compute the strongly connected components of a 6 billion-edge graph in 22 minutes and run applications such as Kleinberg's HITS in real time. This paper describes our techniques for compressing the Link Database, and provides performance numbers for compression ratios and decompression speed.
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
Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., & Wiener, J. (2000) · Computer Networks · doi:10.1016/s1389-1286(00)00083-9 · Cited by 2,810
Self-citation
Cited by
The webgraph framework I: compression techniques
Boldi, P., & Vigna, S. (2004) · Proceedings of the 13th international conference on World Wide Web · doi:10.1145/988672.988752 · Cited by 1,201
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
A Survey on PageRank Computing
Berkhin, P. (2005) · Internet Mathematics · doi:10.1080/15427951.2005.10129098 · Cited by 474
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
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…”
MethodGraph pattern matching revised for social network analysis
Fan, W. (2012) · Proceedings of the 15th International Conference on Database Theory · doi:10.1145/2274576.2274578 · Cited by 176
“, [5, 12, 25, 52, 54]) require to restore original graphs from compressed graphs even to answer simple queries, as observed in [5].”
I/O-efficient techniques for computing pagerank
Chen, Y.-Y., Gan, Q., & Suel, T. (2002) · Proceedings of the eleventh international conference on Information and knowledge management · doi:10.1145/584792.584882 · Cited by 59
What's really new on the web?: identifying new pages from a series of unstable web snapshots
Toyoda, M., & Kitsuregawa, M. (2006) · Proceedings of the 15th international conference on World Wide Web · doi:10.1145/1135777.1135815 · Cited by 21
Metadata
- Authors
- Randall, K. H., Stata, R., Wickremesinghe, R. G., & Wiener, J. L.
- Venue
- Proceedings DCC 2002. Data Compression Conference
- Publisher
- IEEE Comput. Soc
- Published
- 2003-06-25
- Pages
- 122-131
- ISSN
- 1068-0314 (ISSN-L)
- OpenAlex
- W2161088492
- Cited by
- 113
- References
- 1
- FWCI
- 5.89
- 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.