搜索引擎如何在1秒内排名数百万页？

Question

我了解搜索引擎排名的基础知识,包括"反向索引","向量空间模型","余弦相似度","PageRank"等概念.

但是,当用户提交流行的查询字词时,很可能包含此术语的数百万个页面.因此,搜索引擎仍然需要实时对这些数百万页进行排序.例如,我只是尝试在Google中搜索"Barack Obama".它显示"约937,000,000结果(0.49秒)".在0.5秒内排名超过900M项目？这真让我大吃一惊!

搜索引擎如何在1秒内对如此大量的项目进行排序？任何人都可以给我一些直观的想法或指出参考？

谢谢!

更新:

1. 到目前为止,大多数答复(包括一些较旧的讨论)似乎都归功于"反向指数".但是,据我所知,反向索引只能帮助找到"相关页面".换句话说,通过反向索引谷歌可以获得包含"巴拉克奥巴马"的900M页面(超过几十亿页).但是,目前还不清楚如何根据我目前读到的线程"排列"这些数百万的"相关页面".
2. MapReduce框架不太可能成为实时排名的关键组件. MapReduce专为批量任务而设计.在向MapReduce框架提交作业时,响应时间通常至少为一分钟,这显然太慢,无法满足我们的请求.

Answer 1

如果我们确定排名是完整的,那么问题就非常重要.所提供的订购很可能是近似的.

鉴于排名结果的流动性,看起来不合理的答案可能被认为是不正确的.例如,如果网页的整个部分被排除在最高结果之外,您将不会注意到,只要它们稍后包含在内.

这为开发人员提供了几乎所有其他域中完全不可用的自由度.

要问的真正问题是 - 结果与每页分配的实际排名有多精确相符？

Answer 2

有两个主要因素会影响您从搜索引擎获得响应所需的时间.

首先,如果您将索引存储在硬盘上.如果您正在使用数据库,那么您很可能至少使用了硬盘.从冷启动开始,您的查询将很慢,直到这些查询所需的数据被拉入数据库缓存.

另一个是为您的热门查询提供缓存.搜索查询所需的时间比从缓存返回结果要长得多.现在,磁盘的随机访问时间太慢,因此需要将它存储在RAM中.

为了解决这两个问题,Google使用了memcached.这是一个缓存Google搜索引擎输出并向用户提供稍微旧结果的应用程序.这很好,因为大多数时候网络变化不够快,不足以成为一个问题,并且由于搜索的重叠.你几乎可以保证巴拉克奥巴马最近一直在搜查.

影响搜索引擎延迟的另一个问题是网络开销.谷歌一直在使用Linux(IIRC)的自定义变体,该变体已经过优化,可用作Web服务器.他们设法减少了开始将结果转换为查询所花费的时间.

在查询到达其服务器的那一刻,即使在Google处理完查询条件之前,服务器也会立即使用HTTP响应的标头向用户做出响应.

我相信他们也有一堆其他的伎俩.

编辑:他们还保留了已经从索引过程中排序的倒排列表(处理一次比每次查询更好).

使用这些预先排序的列表,最昂贵的操作是列表交集.虽然我很确定谷歌不依赖于向量空间模型,但是列表交集并不是它们的一个因素.

根据文献得到最好回报的模型是概率模型.例如,您可能希望查看Okapi BM25.在我的研究领域(XML检索)中,它在实践中表现相当不错.使用概率模型时,一次处理文档而不是一次处理文档往往效率更高.这意味着我们不是获取包含术语的所有文档的列表,而是查看每个文档,并根据查询中包含的术语对其进行排名(跳过没有术语的文档).

但是如果我们想要变得聪明,我们可以用不同的方式处理问题(但只有当它看起来更好时).如果有一个非常罕见的查询字词,我们可以先排名,因为它影响最大.然后我们按照下一个最佳术语进行排名,并继续,直到我们确定该文档是否可能在我们的前k个结果中.

Answer 3

一种可能的策略是排名前k而不是整个列表.

例如,要通过选择算法找到100万次点击的前100个结果,时间复杂度为O(n log k).由于k = 100且n = 1,000,000,实际上我们可以忽略log(k).

现在,你只需要O(n)就能获得100万次点击中的前100个结果.