М. Абрамзон - Яндекс для всех

Источник: "Принципы работы поисковой машины Рамблер" (http://www.rambler.ru/doc/architecture.shtml).

А вот что рассказывали о решении аналогичных задач на Яндексе.

Если применить к поиску на Яндексе традиционные термины Distributed Information Retrieval, то можно выделить следующие приемы распараллеливания.

1. Разделение коллекции документов— начиная с весны 2000 года, в Яндексе используется "параллельный поиск" в нескольких поисковых источниках. Параллельный поиск — это одновременный поиск в специализированных базах (коллекциях), предлагаемых поисковой системой. Обычно, источник — это отдельная база небольшого размера, отличная от "большой" базы документов. Подразумевается, что документы, индексируемые в такой базе, имеют некоторую регулярную структуру. Если при поиске по обычной базе находятся и документы из базы параллельного поиска, точно соответствующие запросу, то одновременно (параллельно) с обычным результатами поиска выдается список из нескольких найденных документов. База параллельных источников имеет существенно меньший размер, чем база веб-поиска. Обход и индексация документов в ней осуществляется отдельным роботом, поэтому обновление базы может происходить очень быстро (вплоть до ежеминутного).

В "Яндексе" есть четыре базы параллельного поиска:

• по новостям (обновление каждые 10 минут, ежедневно около 3000 новостей);

• по товарным предложениям интернет-магазинов (ежедневное обновление, примерно 300 000 товаров);

• по заголовкам статей энциклопедий (обновление раз в месяц, около 200 000 статей);

• по каталогу ("ручному" описанию веб-ресурсов).

Особый интерес с точки зрения традиционных поисковых технологий представляет техника разделения большой базы документов, то есть собственно базы веб-страниц. По состоянию на 2002 год она состояла из 60 млн документов и была разделена на 30 частей.

Среди особенностей текущей реализации разделения веб-коллекции в Яндексе можно отметить следующее:

• есть центр контроля и распределения URL;

• отсутствует репликация коллекции по машинам;

• распределение документов по коллекциям случайно.

2. Первая фаза обработки запроса: выбор коллекции, трансформации запроса— пользователь может явно указать, в какой коллекции следует искать. Если этого не сделано, то на основе лингвистического (точнее, эвристического) анализа запроса Яндекс может сделать допущение о приоритете специализированной коллекции или подходящей к характеру запроса рубрики каталога.

3. Вторая фаза обработки запроса: раздача запроса по коллекциям— обычно используются все коллекции. Собирающий сервер раздает в коллекции модифицированные запросы, в которых для каждого термина сообщается глобальное значение его обратной частоты (IDf в терминах традиционного IR). Для этого на всех "собирающих" серверах хранится глобальная статистика терминов. Она изменяется медленно, поэтому обновляется относительно редко. Статистика подсчитывается по считающейся наиболее универсальной — вебовской — коллекции. Таким образом, каждая поисковая машина ищет ответ на запрос с назначенными "сверху" глобальными частотами, и значения релевантности, вычисляемые в разных коллекциях, можно считать последовательными и вычисляемыми "в одной системе координат". Модификации запросов этим не ограничиваются, и для специализированных коллекций (например, "энциклопедии") могут быть и другими, в том числе и очень специфическими.

4. Третья фаза обработки запроса: исполнение и ранжирование запроса в коллекциях— запрос выполняется паралельно для всех коллекций.

Следует отметить, что веб-коллекции документов распределены по машинам произвольно и, вообще говоря, могут быть расположены все вместе на одной машине. Слияние результатов производится на том из собирающих (метапоисковых) веб-серверов, на который попадал пользователь при заходе по адресу www.yandex.ru. Процесс раздачи запроса, описанный здесь, позволяет корректно ранжировать слитый результат. При этом не требуется переранжирование результатов, полученных из разных неоднородных коллекций с использованием локальных IDF, а также не нужен динамический обмен данными между источниками для вычисления глобальнойIDF.

Мы ищем в Яндексе информацию и новости, картинки и значения слов, товары и услуги. На сегодняшний день в базе данных накоплена информация о миллионах документов и сайтов, огромном количестве новостей, графических изображений, сотнях тысяч предлагаемых товаров и услуг. За обновление информации в ней отвечают различные роботы.