4

考虑以下搜索结果：

好的。页面是索引的，只需要查找索引表中的计数和前几项，速度是可以理解的。

现在考虑使用 AND 操作进行以下搜索：

这让我很兴奋 ;) 搜索引擎到底如何才能如此快地获得对巨大数据集进行 AND 运算的结果？我看到以下两种执行任务的方法，它们都很糟糕：

  1. 你进行了“大卫”的搜索。拿起巨大的临时表并在其上搜索“John”。但是，临时表没有被“John”索引，因此需要蛮力搜索。无论您拥有什么硬件，这都不会在 0.25 秒内计算出来。
  2. 通过所有可能的单词组合（如“David John”）进行索引。然后我们面临着密钥数量的组合爆炸，甚至谷歌也没有存储容量来处理它。

您可以将任意数量的搜索词组合在一起，并且您仍然可以在 0.5 秒内获得答案！如何？

4

4 回答 4

2

Markus 所写的关于 Google 在多台机器上并行处理查询的内容是正确的。

此外，还有一些信息检索算法使这项工作更容易一些。执行此操作的经典方法是构建一个倒排索引，该索引由发布列表组成- 按顺序列出包含该术语的所有文档的每个术语的列表。

当搜索包含两个词的查询时，从概念上讲，您将获取两个词（“david”和“john”）中的每一个的发布列表，然后沿着它们走，寻找两个列表中的文档。如果两个列表的排序方式相同，则可以在 O(N) 中完成。当然，N 仍然很大，这就是为什么这将在数百台机器上并行完成。

此外，可能还有其他技巧。例如，如果排名最高的文档在列表中的位置较高，那么算法可能会决定它找到了 10 个最佳结果，而无需遍历整个列表。然后它会猜测剩余的结果数量（基于两个列表的大小）。

于 2010-02-26T10:34:53.953 回答
1

我不知道谷歌是怎么做的，但是当客户需要类似的东西时，我可以告诉你我是怎么做的：

如 Avi 所述，它以倒排索引开始。这只是一个表格，列出了每个文档中的每个单词、文档 ID、单词以及单词在该文档中的相关性的分数。（另一种方法是单独索引单词的每个外观及其位置，但在这种情况下不需要这样做。）

从那里开始，它甚至比 Avi 的描述更简单 - 无需对每个术语进行单独搜索。标准的数据库汇总操作可以轻松地一次性完成：

SELECT document_id, sum(score) total_score, count(score) matches FROM rev_index
WHERE word IN ('david', 'john') GROUP BY document_id HAVING matches = 2
ORDER BY total_score DESC

这将返回对“大卫”和“约翰”都有分数的所有文档的 ID（即，两个单词都出现），按相关性近似排序，并且无论有多少或多少都需要大约相同的时间来执行您正在寻找的术语，因为IN性能受目标集大小的影响不大，并且它使用一个简单的方法count来确定所有术语是否匹配。

请注意，这种简单的方法只是将“大卫”分数和“约翰”分数相加来确定整体相关性；它不需要订单/接近/等。的名字考虑在内。再一次，我确信谷歌确实将其纳入他们的分数，但我的客户并不需要它。

于 2010-02-26T11:34:32.050 回答
1

我认为您从错误的角度解决问题。

谷歌在一台机器上没有表格/索引。相反，他们在服务器上大量划分数据集。报告表明，每个查询都涉及多达 1000 台物理机！

凭借如此多的计算能力，“简单”（具有高度讽刺意味）确保每台机器在几分之一秒内完成工作。

阅读有关 Google 技术和基础架构的信息非常鼓舞人心且具有很高的教育意义。我建议阅读BigTable、MapReduce和Google File System。

谷歌有一个他们的出版物档案，里面有很多关于他们技术的有趣信息。metafilter 上的这个帖子还提供了一些关于运行搜索引擎所需的大量硬件的见解。

于 2010-02-26T10:10:26.450 回答
0

我在 16 位机器上做了与几年前类似的事情。该数据集的上限约为 110,000 条记录（它是一个墓地，因此对墓葬的限制有限）所以我设置了一系列位图，每个位图包含 128K 位。

搜索“david”导致我在其中一个位图中设置了相关位，以表示该记录中包含“david”一词。在第二个位图中对“约翰”做了同样的事情。

然后，您需要做的只是两个位图的二进制“与”，生成的位图会告诉您哪些记录号同时包含“david”和“john”。快速扫描生成的位图会为您返回匹配这两个术语的记录列表。

不过，这种技术不适用于谷歌，所以考虑一下我的价值 0.02 美元。

于 2010-02-26T09:51:12.117 回答