Я понимаю основы ранжирования поисковых систем, включая идеи "обратного индекса", "векторной космической модели", "косинусоидальности", "PageRank" и т.д.
Однако, когда пользователь представляет популярный запрос, очень вероятно, что миллионы страниц, содержащих этот термин. В результате поисковой системе по-прежнему необходимо сортировать эти миллионы страниц в режиме реального времени. Например, я просто попытался найти "Барака Обаму" в Google. Он показывает "Около 937 000 000 результатов (0,49 секунды)". Рейтинг более 900 млн. Единиц в течение 0,5 секунд? Это действительно смущает меня!
Как поисковая система сортирует такое большое количество элементов в течение 1 секунды? Может ли кто-нибудь дать мне некоторые интуитивные идеи или указать ссылки?
Спасибо!
ОБНОВЛЕНИЕ:
Одна возможная стратегия - просто ранг top-k, а не весь список.
Например, чтобы найти 100 лучших результатов из 1 миллиона просмотров, алгоритм выбора, сложность времени - O (n log k). Поскольку k = 100 и n = 1,000,000, на практике мы могли бы игнорировать log (k).
Теперь вам нужно только O (n), чтобы получить 100 лучших результатов из 1 миллиона просмотров.
Есть два основных фактора, которые влияют на время, необходимое для получения ответа от вашей поисковой системы.
Во-первых, если вы сохраняете свой индекс на жестком диске. Если вы используете базу данных, очень вероятно, что вы используете жесткий диск хотя бы немного. После холодного загрузки ваши запросы будут медленными, пока данные, необходимые для этих запросов, не будут выгружены в кэш базы данных.
Другой имеет кеш для ваших популярных запросов. Требуется намного больше времени для поиска запроса, чем для возврата результатов из кеша. Теперь время произвольного доступа к диску слишком медленное, поэтому им необходимо сохранить его в ОЗУ.
Чтобы решить обе эти проблемы, Google использует memcached. Это приложение, которое кэширует вывод поисковой системы Google и передает пользователям несколько старых результатов. Это прекрасно, потому что большую часть времени веб-сайт не изменяется достаточно быстро, чтобы это было проблемой, и из-за значительного совпадения в результатах поиска. Вы можете быть почти уверены, что Барака Обаму обыскали недавно.
Другая проблема, которая влияет на задержку поисковой системы, - это сетевые накладные расходы. Google использует пользовательский вариант Linux (IIRC), который был оптимизирован для использования в качестве веб-сервера. Им удалось сократить время, затрачиваемое на то, чтобы начать опрос результатов.
В тот момент, когда запрос попадает на их серверы, сервер немедленно отвечает пользователю заголовком ответа HTTP, даже до того, как Google завершит обработку условий запроса.
Я уверен, что у них тоже есть куча других трюков.
EDIT: Они также сохраняют свои перевернутые списки отсортированными уже из процесса индексирования (лучше обрабатывать один раз, чем для каждого запроса).
С этими предварительно отсортированными списками наиболее дорогостоящей операцией является перекресток списка. Хотя я уверен, что Google не полагается на модель векторного пространства, поэтому перекресток списка не является для них фактором.
Модели, которые окупают лучшее в соответствии с литературой, являются вероятностными моделями. Например, вы можете посмотреть Okapi BM25. Это довольно хорошо на практике в моей области исследований (XML Retrieval). При работе с вероятностными моделями, как правило, гораздо эффективнее обрабатывать документ за раз, а не по времени. Это означает, что вместо того, чтобы получать список всех документов, содержащих термин, мы смотрим на каждый документ и оцениваем его на основе терминов, содержащихся в нашем запросе (пропуская документы, которые не имеют условий).
Но если мы хотим быть умными, мы можем подойти к проблеме по-другому (но только тогда, когда она окажется лучше). Если есть запрос, который встречается крайне редко, мы можем оценивать его первым, потому что он имеет наибольшее влияние. Затем мы оцениваем следующий лучший термин, и продолжаем, пока не определим, может ли этот документ быть в наших лучших результатах.
Вопрос был бы действительно актуальным, если бы мы были уверены, что рейтинг был завершен. Вполне возможно, что предоставленное упорядочение является приблизительным.
Учитывая текучесть результатов ранжирования, никакой ответ, который выглядит разумным, можно считать неправильным. Например, если весь раздел сети был исключен из лучших результатов, вы не заметите, если они будут включены позже.
Это дает разработчикам степень широты, недоступную практически во всех других доменах.
Реальный вопрос - , насколько точно результаты соответствуют фактическому рангу, присвоенному каждой странице?
Здесь вы идете, я искал его для вас, и это то, что я нашел! http://computer.howstuffworks.com/internet/basics/search-engine.htm
Также я предполагаю, что использование баз данных NoSQL вместо RDBMS помогает.
Базы данных NoSQL масштабируются горизонтально лучше и не создают узких мест. Большие парни, такие как Google Facebook или Twitter, используют их.
Как и другие комментарии/ответы, данные могут быть уже отсортированы, и они возвращают смещения найденных данных, а не всей партии.
Реальный вопрос заключается не в том, как быстро они сортируют так много результатов, но как они это делают, когда десятки или сотни миллионов людей во всем мире одновременно обращаются к Google, xD
Как сказал Сяо, просто ранжируйте top-k, а не весь список.
Google сообщает, что есть 937 000 000 результатов, но они не покажут их вам. Если вы продолжаете прокручивать страницу за страницей, через некоторое время она усекает результаты:)
Это моя теория... Его очень невозможно, что вы первый парень, который ищет ключевое слово. Поэтому для каждого ключевого слова (или комбинации), ищущего в поисковой системе, он поддерживает хеш ссылок на релевантные веб-страницы, Каждый раз, когда вы нажимаете ссылку в результатах поиска, она получает голосование по хэш-настройке этой комбинации ключевых слов. К сожалению, если вы первый парень, он сохраняет ваше ключевое слово для поиска (для поиска будущих поисков) и запускает хэширование этого ключевого слова. Таким образом, вы получаете меньше или вообще никаких результатов. Ранжирование страницы, поскольку вы, возможно, знаете, зависит от многих других факторов, таких как обратные ссылки, нет. Страницы, ссылающиеся на ключевое слово в море. и др.
Относительно вашего обновления:
Структура MapReduce вряд ли станет ключевым компонентом для ранжирования в реальном времени. MapReduce предназначен для пакетных задач. При отправке задания в каркас MapReduce время отклика обычно составляет не менее минуты, что, по-видимому, слишком медленное, чтобы удовлетворить наш запрос.
MapReduce предназначен не только для пакетных задач. Существует довольно много каркасов MapReduce, поддерживающих вычисления в реальном времени: Apache Spark, Storm, Infinispan Distributed Executor, Служба рассылаемого сервиса Hazelcast.
Вернуться к вашему вопросу MapReduce - это ключ к распределению задачи запроса для нескольких узлов, а затем объединение результата вместе.
Здесь вы не можете получить точный ответ на этот вопрос;) В любом случае, здесь несколько вещей, которые следует учитывать - Google использует уникальную инфраструктуру во всех ее частях. Мы даже не можем догадаться о сложности сложности их сетевого оборудования или хранилища баз данных. Это все, что я знаю об аппаратном компоненте этой проблемы.
Теперь, для реализации программного обеспечения - как и имя, это означает, что PageRank является рангом. Он не оценивает страницы при вводе поискового запроса. Я полагаю, что каждый час он оценивает его на полностью независимой части инфраструктуры. И мы уже знаем, что роботы-искатели Google перемещаются по Интернету 24/7, поэтому я предполагаю, что новые страницы добавляются в "несортированную" хэш-карту, а затем они ранжируются при следующем запуске алгоритма.
Затем, когда вы вводите запрос, тысячи процессоров независимо сканируют тысячи разных частей базы данных PageRank с коэффициентом разрыва. Например, если коэффициент разрыва равен 10, одна машина запрашивает часть базы данных с значениями PageRank от 0 до 9.99, другая запрашивает базу данных с 10-19.99 и т.д. Поскольку ресурсы не являются препятствием для Google, они могут установить (например, 1), чтобы каждая машина запрашивала менее 100 тыс. страниц, что мало для их аппаратного обеспечения. Затем, когда им нужно скомпилировать результаты вашего запроса, так как они знают, какая машина занимает именно ту часть базы данных, которую они могут использовать 'заполнить пул '. Пусть n - количество ссылок на каждой странице Google. Алгоритм, который объединяет страницы, возвращаемые из запросов, запускался на всех этих машинах по всем различным частям базы данных, должен заполнить только первые n результаты. Таким образом, они берут результаты от машины, запрашивающей самый высокий ранг базы данных. Если это больше, чем n, они будут выполнены, если они не перейдут на следующий компьютер. Это занимает только O (q * g/r), где s - количество страниц, обслуживаемых Google, g - коэффициент разрыва и r - это наивысшее значение PageRank. Это предположение приветствуется тем фактом, что при обращении ко второй странице ваш запрос выполняется еще раз (обратите внимание на другое время, затраченное на его создание).
Это всего лишь мои два цента, но я думаю, что я довольно точно согласен с этой гипотезой.
EDIT: вы можете проверить это для сложности запросов высокого порядка.
У меня для вас есть один ответ: QuickSort!
Я не знаю, что Google действительно делает, но, безусловно, они используют аппроксимацию. Например, если поисковым запросом является "Поисковая машина", тогда число результатов будет = (количество документов, в которых имеется одно или несколько случаев появления слова "поиск" + количество документов, в которых имеется одно или несколько случаев слово "двигатель" ). Это может быть сделано в O (1) сложности времени. Подробнее читайте основную структуру Google http://infolab.stanford.edu/~backrub/google.html.