17

了解搜索引擎排名的基础知识，包括“反向索引”、“向量空间模型”、“余弦相似度”、“PageRank”等思想。

但是，当用户提交一个热门查询词时，很可能有数百万个页面包含该词。因此，搜索引擎仍然需要对这数百万个页面进行实时排序。例如，我刚刚尝试在 Google 中搜索“Barack Obama”。它显示“大约 937,000,000 个结果（0.49 秒）”。在 0.5 秒内排名超过 9 亿个项目？这真的让我大吃一惊！

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

谢谢！

更新：

  1. 到目前为止，大多数回应（包括一些较早的讨论）似乎都将功劳归功于“反向索引”。但是，据我所知，反向索引仅有助于找到“相关页面”。换句话说，通过反向索引，谷歌可以获得包含“巴拉克奥巴马”的 9 亿页（超过数十亿页）。但是，目前还不清楚如何根据我目前阅读的线程对这数百万个“相关页面”进行“排名” 。
  2. MapReduce 框架不太可能成为实时排名的关键组件。 MapReduce 专为批处理任务而设计。当向 MapReduce 框架提交作业时，响应时间通常至少为一分钟，这显然太慢了，无法满足我们的要求。
4

11 回答 11

8

如果我们确定排名是完整的，那么这个问题将非常相关。提供的排序很可能是近似的。

鉴于排名结果的流动性，任何看起来合理的答案都不会被认为是不正确的。例如，如果网络的整个部分被排除在最热门的结果之外，您不会注意到，前提是它们后来被包括在内。

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

要问的真正问题是 -结果与分配给每个页面的实际排名匹配的精确程度如何？

于 2013-11-05T11:13:03.807 回答
6

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

第一个是如果您将索引存储在硬盘上。如果您使用的是数据库，那么您很可能至少使用了一点硬盘。从冷启动开始，您的查询会很慢，直到这些查询所需的数据被拉入数据库缓存。

另一个是为您的热门查询提供缓存。搜索查询比从缓存中返回结果要花费更长的时间。现在，磁盘的随机访问时间太慢了，所以他们需要将它存储在 RAM 中。

为了解决这两个问题，Google 使用了 memcached。它是一个缓存 Google 搜索引擎的输出并向用户提供稍微旧的结果的应用程序。这很好，因为大多数时候网络的变化速度不够快，不会成为问题，而且搜索中存在大量重叠。您几乎可以肯定巴拉克奥巴马最近已被搜索。

影响搜索引擎延迟的另一个问题是网络开销。Google 一直在使用 Linux (IIRC) 的自定义变体，该变体已针对用作 Web 服务器进行了优化。他们设法减少了开始将结果转为查询所需的一些时间。

查询到达其服务器的那一刻，服务器会立即使用 HTTP 响应的标头向用户做出响应，甚至在 Google 完成对查询词的处理之前。

我敢肯定他们还有很多其他的花招。

编辑：他们还保持他们的倒排列表已经从索引过程中排序（最好处理一次而不是每个查询）。

使用这些预先排序的列表，最昂贵的操作是列表交集。虽然我相当确定谷歌不依赖向量空间模型，但列表交集对他们来说并不是一个因素。

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

但如果我们想变得聪明，我们可以用不同的方式来解决问题（但只有当它看起来更好时）。如果有一个非常罕见的查询词，我们可以将它排在第一位，因为它具有最高的影响力。然后我们使用下一个最佳术语进行排名，并继续进行，直到我们确定该文档是否有可能在我们的前 k 个结果中。

于 2013-11-04T13:24:18.713 回答
5

一种可能的策略是仅对前 k 名而不是整个列表进行排名。

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

现在，您只需要 O( n ) 即可获得 100 万次点击中的前 100 个结果。

于 2013-10-21T14:19:34.630 回答
1

我也猜想使用 NoSQL 数据库而不是 RDBMS 会有所帮助。

NoSQL 数据库可以更好地横向扩展，并且不会产生瓶颈。像 Google Facebook 或 Twitter 这样的大人物使用它们。

正如其他评论/答案所暗示的那样，数据可能已经排序，并且它们正在返回找到的数据的偏移量，而不是整个批次。

真正的问题不是他们如何快速对这么多结果进行排序，而是当全世界数以千万计或数亿人同时查询谷歌时，他们如何做到这一点xD

于 2013-10-21T14:29:18.327 回答
1

正如肖所说，只需排名前k而不是整个列表。

谷歌告诉你有 937,000,000 个结果，但它不会全部显示给你。如果你继续滚动页面，一段时间后它会截断结果:)

于 2013-11-06T14:27:45.107 回答
0

我不知道谷歌真正做了什么，但他们肯定使用近似值。例如，如果搜索查询是“搜索引擎”，那么结果数将为 =（出现一次或多次“搜索”一词的文档数 + 出现一次或多次“引擎”这个词）。这可以在 O(1) 时间复杂度内完成。有关详细信息，请阅读 Google http://infolab.stanford.edu/~backrub/google.html的基本结构。

于 2013-11-21T03:39:10.893 回答
0

给你，我帮你查了一下，这就是我发现的！http://computer.howstuffworks.com/internet/basics/search-engine.htm

于 2013-10-03T14:42:33.977 回答
0

这就是我的理论...您是第一个搜索关键字的人是极不可能的。因此，对于在搜索引擎上搜索到的每个关键字（或组合），它都会维护指向相关网页的链接哈希。每次您单击搜索结果中的链接时，都会对该关键字组合的哈希集进行投票。不幸的是，如果您是第一个人，它会保存您的搜索关键字（用于建议将来的搜索）并开始对该关键字进行哈希处理。所以你最终得到的结果更少或根本没有。您可能知道的页面排名取决于许多其他因素，例如反向链接，不。在 seaech 中引用关键字的页面。等等

于 2013-11-06T14:08:13.250 回答
0

你不可能期望在这里得到这个问题的准确答案；）无论如何，这里有几件事需要考虑——谷歌在它的每个部分都使用了独特的基础设施。我们甚至无法猜测他们的网络设备或数据库存储的复杂程度。这就是我所知道的关于这个问题的硬件部分的全部信息。

现在，对于软件实施——就像名字所说的那样，PageRank 本身就是一个排名。当您输入搜索查询时，它不会对页面进行排名。我假设它每小时都将它排在基础架构的一个完全独立的部分。我们已经知道谷歌爬虫机器人正在 24/7 漫游网络，所以我假设新页面被添加到“未排序”的哈希图中，然后在算法的下一次运行中对它们进行排名。

接下来，当您键入查询时，数千个 CPU 会以间隔因子独立扫描 PageRank 数据库的数千个不同部分。例如，如果间隔因子为 10，则一台机器查询数据库中 PageRank 值为 0-9.99 的部分，另一台查询数据库中的 10-19.99 等。由于资源不是 Google 的障碍，因此它们可以设置间隔因子如此之低（例如 1），以便每台机器查询少于 100k 的页面，这对于它们的硬件来说并不算多。然后当他们需要编译你的查询结果时，因为他们知道哪台机器准确地对数据库的哪一部分进行排名，他们可以使用“填充池”原则。让n是每个 Google 页面上的链接数。组合从查询返回的页面的算法在所有这些机器上针对数据库的所有不同部分运行，只需要填充前n 个结果。因此，他们从机器查询数据库的最高级别获取结果。如果它大于n，他们就完成了，如果不是，他们移动到下一台机器。这只需要O(q*g/r)，其中s是 Google 服务的页面数量，g是间隔因子，r是 PageRank 的最高值。当您转到第二页时，您的查询再次运行（注意生成它所花费的不同时间）这一事实鼓励了这种假设。

这只是我的两分钱，但我认为我对这个假设非常准确。

编辑：您可能想检查一下高阶查询的复杂性。

于 2013-11-06T17:05:07.963 回答
0

关于您的更新：

MapReduce 框架不太可能成为实时排名的关键组件。MapReduce 专为批处理任务而设计。当向 MapReduce 框架提交作业时，响应时间通常至少为一分钟，这显然太慢了，无法满足我们的要求。

MapReduce 不仅仅是为批处理任务设计的。支持实时计算的 MapReduce 框架有很多：Apache Spark、Storm、Infinispan Distributed Executor、Hazelcast Distributed Executor Service。

回到你的问题 MapReduce 是将查询任务分发到多个节点，然后将结果合并在一起的关键。

于 2013-11-06T16:01:05.927 回答
-1

我给你一个字的答案：快速排序！

于 2013-11-06T18:01:21.520 回答