扫码加入数据分析学习群

假设Web有40亿个页面，每个页面都有10个指向其他页面的链接。在最简单的形式中，我们需要32位或4个字节来指定每个链接的每个末端（源和目标），总共需要

（250）

内存字节。可以利用Web图的一些基本属性在10％的内存要求下使用。乍一看，我们似乎有一个数据压缩问题 - 适用于各种标准解决方案。但是，我们的目标不是简单地压缩Web图形以适应内存;我们必须以有效支持连接查询的方式这样做;这一挑战让人联想到索引压缩（第5章）。

我们假设每个网页都由一个唯一的整数表示; 用于分配这些整数的具体方案如下所述。我们建立了一个类似于倒排索引的邻接表：每个网页都有一行，其行按相应的整数排序。任何页面的行都包含一个整数的排序列表，每个整数对应一个链接到的网页。此表允许我们回复页面链接到

的表单的查询？以类似的方式，我们构建一个表，其条目是链接到的页面。该表格表示将天真表示（其中我们通过其两个端点，每个端点，每个32位整数）明确表示每个链接所占用的空间减少50％。下面我们将重点描述该表的链接从每一页; 应该清楚的是，这些技术同样适用于每个页面的链接表。为了进一步减少表的存储空间，我们利用了几个想法：

1. 列表之间的相似性：表的许多行有许多共同的条目。因此，如果我们明确地表示几个相似行的原型行，则剩余部分可以简洁地表示为原型行。
2. 地点：从页面到页面的许多链接转到“附近”页面 - 例如，同一主机上的页面。这表明在编码链接的目的地时，我们通常可以使用小整数，从而节省空间。
3. 我们在排序列表中使用间隙编码：不是存储每个链接的目的地，而是存储行中前一个条目的偏移量。