Анатомия системы крупномасштабного гипертекстового интернет-поиска

Сергей Брин и Лоуренс Пейдж

Кафедра информационных технологий Стенфордского университета, Стенфорд, CA 94305, США

sergey@cs.stanford.edu и page@cs.stanford.edu

Аннотация

В этой работе мы представляем Google,
прототип крупномасштабной поисковой машины, которая активно использует структуру
гипертекста. Google предназначена для эффективного поиска и индексирования Интернета,
и обеспечения более удовлетворительных результатов поиска, чем у существующих
систем. Прототип с полным текстом и списком гиперссылок, по крайней мере, 24 миллионов страниц можно найти на google.stanford.edu.
Проектирование поисковой системы является сложной задачей. Поисковые системы
индексируют десятки и сотни миллионов веб-страниц с достаточно большим числом
различных терминов. Они отвечают на десятки миллионов запросов каждый день.
Несмотря на важность крупномасштабных поисковых систем в Интернете, сравнительно
мало научных исследований было проведено по данной тематике. Кроме того, из-за
быстрого развития технологий и распространения Интернета, создание системы
веб-поиска в настоящее время довольно сильно отличается от трехлетней давности.
В данном документе приводится максимально подробное описание наших
крупномасштабных поисковых систем на сегодняшний день. Помимо проблем
масштабирования традиционными методами поиска данных такого масштаба,
появляются новые технические проблемы, связанные с использованием дополнительного
представления информации в гипертексте для получения лучших результатов поиска.
В этой статье рассматривается данный вопрос создания практической
крупномасштабной системы, которая может использовать дополнительную информацию,
представленную в гипертексте. Также мы рассмотрим проблему – как эффективно
бороться с неконтролируемыми гипертекстовыми наборами, где любой желающий может
опубликовать всё, что хочет.

Ключевые слова: Интернет, поисковые машины, информационный поиск, PageRank, Google.

1. Вступление

(Примечание:
существуют две опубликованные версии данной работы – полная и сокращенная печатная версия. Полная
версия доступна в Интернете и записи конференции на CD-ROM)
.
Интернет создает новые задачи для поиска информации. Количество информации в
сети растет быстро, также как и количество новых пользователей, которым трудно
найти нужную информацию. Люди, который пользуются Интернетом, применяя граф ссылок,
часто начинают работу с высококачественных ручных поисковых машин, таких как
Yahoo!. Полученные наборы страниц содержат много популярных тем, но эти наборы субъективные,
их создание и поддержка дорого обходятся, они медленно улучшаются и не могут
охватить все скрытые темы. Автоматизированные поисковые системы, которые
полагаются на соответствия ключевых слов обычно выдают слишком много результатов
низкого качества. Что ещё хуже, некоторые рекламодатели пытаются привлечь к
себе внимание людей, принимая меры, которые вводят в заблуждение
автоматизированные поисковые системы. Мы создали крупномасштабную поисковую
машину, которая решает многие проблемы существующих систем. Это обусловливает
интенсивное использование дополнительной структуры, находящейся в гипертексте, для
обеспечения гораздо более высокого качества результатов поиска. Мы выбрали имя для
нашей системы – Google, потому что оно является искаженным написанием googol,
или 10100 и хорошо вписывается в нашу цель создания сверхбольших
поисковых систем.

1.1. Поисковая веб-машина – увеличение масштабирования: 1994 — 2000

Технологиям поисковой машины пришлось
резко масштабироваться, чтобы идти в ногу с ростом Интернета. В 1994 году одна
из первых поисковых систем, червь во всемирной сети Интернет (WWWW) [Мак Бриан
94] имела индекс из 110 000 веб-страниц и веб-доступных документов. По
состоянию на ноябрь 1997 года, лидеры поисковых систем заявили об индексах от
2000000 (WebCrawler) до 100 миллионов веб-документов (Search Engine Watch).
Можно предположить, что к 2000 году, всеобъемлющий индекс Web будет содержать
более миллиарда документов. В то же время, количество запросов от ручных
поисковых систем также фантастически вырастет. В марте и апреле 1994 года WWWW получала в среднем около 1500 запросов в день. В ноябре 1997 года Altavista заявила, что
обрабатывает примерно 20 миллионов запросов в день. С растущим числом пользователей
в Интернете и автоматизированных систем, которые подают запросы в поисковые
системы, вполне вероятно, что основные поисковые системы будут обрабатывать
сотни миллионов запросов в день к 2000 году. Цель нашей разработки заключается в
решении многих проблем, как по качеству, так и объёму, при помощи
технологии масштабирования поиска столь огромного количества запросов.

1.2. Google: масштабирование всемирной сети

Создание поисковой системы, которая
масштабирует даже современную всемирную сеть, имеет много проблем. Технология
быстрого сканирования должна собирать веб-документы и следить за их актуальным
состоянием. Дисковое пространство должно быть эффективно использовано для
хранения индексов и, возможно, самих документов. Система индексации должна эффективно
обрабатывать сотни гигабайт данных. Запросы должны обрабатываться быстро, со
скоростью от сотен до тысяч в секунду.

Эти задачи становятся всё сложнее по
мере роста Интернета. Тем не менее, производительность системы и затраты
значительно увеличились, частично компенсируя трудности. Есть, однако, несколько
видимых исключений из этого прогресса, таких как время поиска и надёжность
операционной системы. При разработке Google, мы принимали во внимание как
скорость роста Интернета, так и технологические изменения. Google предназначена
для масштабирования довольно крупных наборов данных. Это позволяет экономично использовать память для хранения индекса. Его структура данных оптимизирована
для быстрого и эффективного доступа (см. раздел 4.2). Кроме того, мы ожидаем,
что затраты на индексирование и хранение текста или HTML, в конечном счете, снизятся по отношению к доступному количеству (см. Приложение Б). Это приведет
к успешным результатам масштабирования таких централизованных систем, как
Google.

1.3 Цели проектирования

1.3.1 Улучшение качества поиска

Наша цель заключается в улучшении
качества поисковых машин. В 1994 году, некоторые люди считали, что полный
индекс поиска с легкостью позволяет найти что угодно. Согласно изданию «Лучшее
в веб-сети 1994 – Навигаторы»: «Лучшая навигационная служба должна
сделать легким поиск всего, что есть в Интернете (после того как все данные
введены)». Тем не менее, Интернет в 1997 году совершенно иной. Любой, кто
использовал поисковую систему недавно, может подтвердить, что полнота индекса
не является единственным фактором, определяющим качество результатов поиска.
«Спам-результаты» часто отсеивают любые результаты, в которых заинтересован
пользователь. В самом деле, по состоянию на ноябрь 1997 года, только одна из
четырех крупнейших коммерческих поисковых систем находит себя (включает свою
собственную страницу в первой десятке результатов запроса, включающим ее
название). Одной из основных причин этой проблемы является то, что ряд
документов по индексам увеличивается на много порядков, но у пользователей нет
возможности открыть эти документы. Люди по-прежнему просматривают только первые
несколько десятков результатов.

Из-за этого при увеличении размера
наборов, необходимы инструменты, которые имеют достаточно высокую точность (количество
соответствующих документов в результате поиска, например, в первой десятке
результатов). Действительно, мы хотим, чтобы наше понятие
«соответствующий» включало только самые лучшие документы, так как там
могут быть десятки тысяч низкорелевантных документов. Эта высокая точность важна так же в рамках полноты (общее количество
релевантных документов, которое система может вернуть). Очень мало
уверенности в том, что использование большего количества гипертекстовой информации
может улучшить поиск и другие приложения [Маркиори 97] [Спертус 97]
[Вейс 96] [Клейнберг 98]. В частности, ссылочная структура [стр. 98] и
текстовая ссылка предоставляют много информации для вынесения решений об актуальности и качестве фильтрации. Google использует структуру и текст ссылки
(см. разделы 2.1 и 2.2).

1.3.2 Научное исследование поисковых систем

Помимо непрерывного роста, Интернет также становится всё больше коммерческим. В 1993 году 1,5%
веб-серверов располагались в доменной зоне .com. Эта доля превысила 60% в 1997 году.
В то же время, поисковые системы мигрировали с академических доменов на коммерческие. До сих пор наиболее развитые поисковые системы не уделяли
внимания компаниям с небольшой публикацией о технических деталях. Это является
причиной того, что технология поиска остается в значительной степени «черной
магией» и ориентирована на рекламу (см. Приложение А). С помощью Google, у нас
появилась важная цель по улучшению и развитию научной сферы.

Другой важной целью
проектирования было создание системы, которую могли бы использовать максимальное количество людей. Возможность масштабного использования была важна для нас, потому что мы считаем, что
некоторые из наиболее интересных исследований будут предусматривать активизацию
огромного количества использования данных, которые доступны в современных
веб-системах. Например, количество запросов ежедневно составляет многие десятки
миллионов. Тем не менее, довольно трудно получить эти данные,
главным образом из-за того, что они представляют коммерческую ценность.

Наша конечная цель разработки заключается в создании архитектуры, которая сможет поддерживать новые научные
исследования в крупномасштабных веб-данных. Для поддержки новых
исследований, Google хранит все найденные актуальные документы в сжатом виде.
Одной из наших главных целей в области проектирования Google было создание
среды, в которой другие исследователи могут быстро обрабатывать большие части
Интернета, и выдавать интересные результаты, которые было бы очень трудно
отыскать в противном случае. За короткое время работы системы, ей было
посвящено несколько работ с использованием баз данных, созданных Google, и
многие другие исследования продолжаются по сей день. Другой целью является создание среды, похожей на Spacelab, где исследователи и даже студенты могут предлагать и проводить интересные эксперименты с использованием наших крупномасштабных данных из Интернета.

2. Характеристика системы

Поисковая система
Google имеет две важные особенности, которые помогают ей получать результаты высокой точности. Во-первых, она использует ссылочную структуру Интернета для
расчёта рейтинга каждой веб-страницы. Этот рейтинг называется PageRank и
подробно описан в [Page 98]. Во-вторых, Google использует ссылки для
улучшения результатов поиска.

2.1 PageRank: упорядочивание веб-сети

Граф цитат (ссылок)
сети является важным ресурсом, который в значительной степени не используется
существующими поисковыми машинами. Мы создали карты, содержащие более 518
миллионов данных гиперссылок, и это является значительной выборкой из общего числа ссылок. Эти
карты позволяют быстро вычислить PageRank веб-страницы — объективную метрику важности её упоминания, что вполне соответствует субъективному преставлению
людей о важности. По аналогии, PageRank является отличным способом для
установления приоритетности результатов веб-поиска по ключевым словам, т.е., фактически, он решает задачу ранжирования. Поиск
большинства популярных простых текстов, соответствующих критериям поиска,
который ограничен названием веб-страницы, выполняется превосходно, когда
PageRank расставляет приоритеты результатов (доступна демо-версия на
google.stanford.edu). PageRank так же эффективен при полнотекстовом поиске в основной системе Google.

2.1.1 Описание вычисления PageRank

Научная литература о подсчете цитат была использована применительно к Вебу, в основном, для подсчета цитат или обратных ссылок данной
страницы. Это дает некоторое приближённое значение важности или качества страницы.
PageRank расширяет эту идею, не подсчитывая число ссылок со всех страниц
одинаковым образом, а нормируя количество ссылок на странице. PageRank
определяется следующим образом:

Пусть
страница А имеет страницы T1 … Tn, которые указывают на нее (т. е.
являются цитатами). Параметр d является коэффициентом затухания, который имеет
значения от 0 до 1. Обычно d принимается как 0,85. Более подробная информация
о d приводится в следующем разделе. Кроме того, C(A) определяется как
количество исходящих ссылок с A. PageRank страницы рассчитывается следующим
образом:

Формула PageRank.

Следует
отметить, что PageRank’и образуют распределение вероятностей веб-страниц, так
что сумма PageRank’ов всех веб-страниц будет равна единице.

PageRank или PR(A) может быть рассчитан
с использованием итеративного алгоритма и соответствует главному собственному
вектору нормированной матрицы ссылок сети. Кроме того, PageRank 26 миллионов
веб-страниц может быть вычислен за несколько часов на рабочей станции среднего
размера. Существуют так же многие другие детали расчёта, которые выходят за рамки данной
статьи.

2.1.2 Интуитивная оценка

PageRank можно рассматривать в качестве
модели поведения пользователя. Мы предполагаем, что существует некий «случайный
пользователь», который заходит на веб-страницу (соответственно, в случайном порядке) и
переходит по ссылкам, никогда не нажимая кнопку «вернуться назад», но, в
конце концов, ему надоедает и он переходит на другую случайную страницу.
Вероятность того, что случайный пользователь посетит данную страницу, является его
PageRank. И коэффициент затухания d
является вероятностью того, что на каждой странице «случайный
пользователь» будет скучать и переходить на другую случайную страницу.
Одним из важных изменений является только добавление коэффициента затухания d на одну страницу или группу страниц.
Это даёт возможность персонализации и может сделать почти невозможным
преднамеренное введение системы в заблуждение, чтобы получить более высокий
рейтинг. У нас есть несколько других расширений PageRank, опять же см. [Page 98].

Другая интуитивная оценка состоит в
том, что страница может иметь высокий PageRank, если много страниц ссылаются на неё, или если есть несколько страниц, которые указывают на
неё и имеют высокий PageRank. Очевидно, что страницы, которые хорошо цитируются
по всему Интернету, стоят внимания пользователя. Кроме того, страницы, которые процитированы, например с главной страницы Yahoo!, также заслуживают
внимания. Если страница не была высококачественной, или даже битой ссылкой,
то вполне вероятно, что главная страница Yahoo не будет ссылаться на неё.
PageRank учитывает оба случая (и все промежуточные) путём рекурсивного
распределения весов через структуру ссылок в Интернете.

2.2 Текст ссылки (анкор)

Текст ссылки в нашей поисковой системе
обрабатывается специальным образом. Большинство поисковых систем связывают
текст ссылки с самой страницей. Помимо этого, мы ассоциируем его со страницей, на
которую указывает сама ссылка. Это имеет несколько преимуществ. Во-первых, ссылки
часто обеспечивают более точное описание веб-страницы, чем сама страница.
Во-вторых, ссылки могут существовать для документов, которые не могут быть
проиндексированы текстовой поисковой системой, например, изображений, программ и баз данных. Это позволяет найти веб-страницы, которые не были на самом деле
просканированы. Обратите внимание, что страницы, которые не были
просканированы, могут вызвать проблемы, так как они никогда не проверяются на
достоверность перед выдачей пользователю. В этом случае поисковая
система может даже выдать страницу, которая никогда на самом деле не
существовала, но имела гиперссылки, указывающие на нее. Тем не менее,
результаты можно сортировать, поэтому мы редко встречаемся с данной проблемой.

Идея связи текста ссылки и цитируемой страницы была реализована в World Wide Web Worm [Мак Бриан 94], в особенности потому что она помогает при поиске нетекстовой информации, и расширяет
охват поиска с меньшим количеством загруженных документов. Мы используем
связь ссылок главным образом из-за, что текст ссылки может помочь
обеспечить более качественные результаты. Эффективное использование текста
ссылки технически сложно из-за большого количества данных, которые должны быть
обработаны. В нашем текущем поиске находится 24 млн. страниц и у нас было более 259
миллионов ссылок, которые мы индексировали.

2.3 Другие характеристики

Кроме PageRank и учёта анкоров, Google имеет несколько других особенностей. Во-первых, у него есть
локальная информация обо всех обращениях и это имеет широкое использование в
поиске на расстоянии. Во-вторых, Google отслеживает некоторые элементы
визуальной информации, такие как размер шрифта слова. Слова с большим и жирным
шрифтами имеют больший, чем другие слова, вес. В-третьих, исходный код HTML-страницы доступен в архиве.

3 Смежные работы

Исследований по информационному поиску в Сети было совсем немного. World Wide Web Worm (WWWW) [Мак Бриан 94] была одной из первых поисковых систем Интернета. Затем последовали несколько других научных поисковых систем, многие из которых в настоящее время являются
открытыми акционерными обществами. По сравнению с ростом Интернета и важностью
информационного поиска, насчитывается очень мало работ о современных поисковых системах
[Пинкертон 94]. По словам Майкла Молдина (главного научного сотрудника Lycos
Inc) [Молдин], «различные службы (в том числе Lycos) строго охраняют
подробности этих баз данных». Тем не менее, было достаточно много работ по
индивидуальным особенностям поисковых систем. Особенно широко представлены
работы, которые могут получать результаты от пост-обработки результатов
существующих коммерческих поисковых систем, или разрабатывают мелкомасштабные
«индивидуальные» поисковые системы. Наконец, было много исследований
по информационно-поисковым системам, особенно по хорошо контролируемым наборам.
В следующих двух разделах мы обсудим некоторые сферы, где эти исследования
должны развиваться, чтобы улучшить работу в Сети.

3.1 Информационный поиск

Исследование информационно-поисковых
систем насчитывает много лет и хорошо развивалось [Виттен 94]. Тем не менее,
большинство исследований по информационно-поисковым системам проводились на
небольших хорошо контролируемых однородных коллекциях, таких как сборники научных
трудов или новостей по этой теме. Действительно, Text Retrieval Conference [TREC
96] использует довольно небольшой, хорошо управляемый набор для своих критериев
поиска. «Very Large Corpus» работает всего с 20 Гб по сравнению с 147
Гб нашего сканирования 24 миллионов веб-страниц. То, что хорошо работает на
TREC, часто не приводит к хорошим результатам в Интернете. Например,
стандартная модель векторного пространства пытается вернуть документ, который
наиболее близко соответствует запросу, при условии, что запрос и документ
являются векторами, которые определяются наличием в них слова. В Интернете эта методика часто возвращает очень короткие документы, которые являются самим
запросом с несколькими дополнительными словами. Например, мы наблюдали результат
от основной поисковой системы — страницу, которая содержала только надпись «Билл
Клинтон отстой» и картинку по запросу «Билл Клинтон».
Иногда утверждается, что в Интернете, пользователи должны более
точно формулировать поисковый запрос, дополняя его ключевыми словами. Мы
несогласны с такой позицией. Если пользователь вводит такой запрос, как «Билл Клинтон» он должен получить адекватные результаты,
так как есть огромное количество доступной качественной информации на эту тему.
Рассматривая подобные примеры, мы считаем, что стандартные исследования по поиску
информации должны быть углублены, чтобы эффективно работать в Мировой Сети.

3.2 Разница между Интернетом и хорошо контролируемым набором

Интернет является масштабной коллекцией абсолютно неконтролируемых разнородных документов. Документы в Интернете имеют совершенно различное содержание и мета-данные, доступные извне. Например, по содержанию документы отличаются языком (как человеческим, так и языком программирования),
лексикой (адреса электронной почты, ссылки, почтовые индексы, номера телефонов,
серийные номера изделий), типом или форматом (текст, HTML, PDF, изображения,
звуки) и могут даже генерироваться машиной (файлы регистрации и вывод
информации базы данных). С другой стороны, мы определяем внешнюю мета-информацию
в качестве информации, которая может характеризоваь документ, но не содержаться в нём самом. К примерам внешней мета-информации относятся: достоверность источника,
частота обновления, качество, популярность или использование и цитирование. Не
только возможные источники внешней мета-информации варьируются, но и ее
измеренные составные части также меняются на столько же порядков. Сравните,
например, использование информации на главной страницй Yahoo!, которая в
настоящее время имеет миллионы ежедневных просмотров с запутанными
историческими статьями, которые может быть просмотрена всего несколько раз за много лет. Очевидно, что эти два вопроса должны
рассматриваться в поисковой системе совершенно по-разному.

Еще одним большим различием между
Интернетом и традиционными хорошо контролируемыми наборами является то, что нет
практически никакого контроля над тем, что люди могут выложить в Интернете. Объединение
этой гибкости публикации чего-либо, что имеет огромное влиянием на поисковые
системы, для маршрутизации трафика и компаний, которые сознательно манипулируют
поисковыми системами с целью получения прибыли, стало серьезной проблемой. Эта
проблема не рассматривается в традиционных закрытых
информационно-поисковых системах. Кроме того, интересно отметить, что поисковые
системы терпят неудачи при поиске мета-информации, потому что любой текст на
странице, который непосредственно не представлен пользователю, способен
манипулировать ранжированием. Существуют даже многочисленные компании,
которые специализируются на манипуляции поисковой выдачей для получения
прибыли.

4 Анатомия системы

Для начала мы обсудим архитектуру системы на
высоком уровне. Далее подробно опишем важные структуры данных, а затем подробно рассмотрим основные приложения системы: сканирование, индексация и поиск.

4.1 Обзор архитектуры Google

В этом разделе мы приведем краткий обзор
того, как работает система в целом (рис. 1). В последующих разделах будут
описываться приложения и структуры данных, не упомянутые в этом разделе. В
основном Google реализована на С и С + + для повышения эффективности и может
работать в Solaris или Linux.

Сканирование Интернета в Google (загрузка веб-страниц) осуществляется несколькими распределенным сборщиками (пауками).
Существует URL-сервер, посылающий списки URL-адресов на обработку сборщиками. Веб-страницы, которые обрабатываются, отправляются
на сервер архива. Далее он сжимает и сохраняет веб-страницы в хранилище.
Каждая веб-страница имеет соответствующий идентификационный номер, который
называется docID. Он присваивается, когда система получает новый URL с веб-страницы.
Функция индексирования выполняется индексатором и сортировщиком. Индексатор
выполняет несколько функций. Он обращается к хранилищу, распаковывает документы,
и анализирует их. Каждый документ преобразуется в набор слов, которые
называются «hits». Hits записывает слова, положение в документе,
приблизительный размер шрифта и регистр. Индексатор распределяет эти hits в
набор «бочек», создавая частично отсортированный прямой индекс.
Индексатор выполняет еще одну важную функцию. Он анализирует все ссылки на каждой веб-странице и сохраняет важную информацию о них в файл анкоров. Этот
файл содержит достаточно информации, чтобы определить, откуда и куда ведет
ссылка и текст самой ссылки.


Рисунок 1.
Высокоуровневая архитектура Google.

Рисунок 1. Высокоуровневая архитектура Google.

Определитель URL читает файл ссылок и
преобразует относительные URL-адреса в абсолютные и в свою очередь на docID. Он
помещает анкор ссылки в прямой индекс, связанный с docID, на который указывает ссылка. Он также создаёт базу данных ссылок, которые являются парами docID. База данных ссылок используется для вычисления PageRank всех
документов.

Сортировщик принимает бочки, отсортированные по docID (об этом упрощении см. раздел 4.2.5) и заново сортирует их
по wordID для создания инвертированного индекса. Это делается локально, поэтому
для этой операции не требуется много временного дискового пространства. Сортировщик
также выдает список wordID и отправляет в обратный индекс. Программа под
названием DumpLexicon принимает этот список вместе с набором слов, подобранных индексатором, и создает новый лексикон, который будет использоваться
клиентом поиска. Поисковый клиент работает как веб-сервер и использует набор слов,
созданный DumpLexicon вместе с обратным индексом, и PageRank для ответа на
запросы.

4.2 Основные структуры данных

Структуры данных Google оптимизированы
таким образом, что можно просканировать, проиндексировать и провести поиск
достаточно большого набора документов с небольшими затратами. Несмотря на то, что скорость операций и частота процессоров значительно возросли за последние
годы, по-прежнему доступ к жётсткому диску требует около 10 мс. Google
разрабатывалсся для минимизации обращений к диску и это оказало
значительное влияние на принцип структурирования данных.

4.2.1 BigFiles

BigFiles — виртуальные файлы, распределённые по нескольким файловым системам и доступные по 64-битному целочисленному адресу. Размещение в нескольких файловых системах проводится автоматически. Пакет BigFiles также обрабатывает распределение и освобождение
дескрипторов файлов, так как операционные системы не соответствуют в
достаточной мере нашим потребностям. BigFiles также поддерживают элементарные
опции сжатия.

4.2.2 Хранилище

Хранилище содержит полный код HTML каждой
веб-страницы. Каждая страница сжимается с помощью zlib (см. RFC1950). Выбор
технологии сжатия является компромиссом между скоростью и степенью
сжатия. Мы выбрали zlib по причине его скорости, несмотря на то, что bzip предлагает значительно более высокую степень сжатия. Степень сжатия bzip в хранилище
составляла примерно 4 к 1, по сравнению с 3 к 1 у zlib. В хранилище документы располагаются один за другим и каждму предшествует его docID, длина и URL, как показано на
рисунке 2. Для доступа к хранилищу не требуется дополнительных структур данных. Таким образом, достигается упорядоченность данных и упрощается разработка: мы способны воссоздавать все
прочие структуры данных только из хранилища и файла с ошибками краулера.

Рисунок 2. Структура данных хранилища.

Рисунок 2. Структура данных хранилища.

4.2.3 Индекс документов

Индекс документов (каталог) хранит информацию о
каждом документе. Это индекс фиксированной ширины ISAM (индексно-последовательного
метода доступа), упорядоченный по docID. Информация, хранящаяся в каждой записи,
включает в себя текущее состояние документа, указатель на хранилище, контрольную
сумму документа, а также различные статистические данные. Если документ был
просканирован, он также содержит указатель на файл переменной ширины docinfo, в котором содержится URL и title документа. В противном случае указатель
указывает на список URL, который содержит только URL. Это конструкционное решение
было обусловлено желанием иметь достаточно компактную структуру данных, а также
возможность извлекать запись из одного диска во время поиска.

Кроме того, есть файл, который
используется для преобразования URL в docID. Это список контрольных сумм URL с
соответствующими docID, который сортируется по контрольной сумме. Для того чтобы
найти docID конкретного URL, вычисляется контрольная сумма URL и выполняется
бинарный поиск в файле контрольных сумм. URL-адреса
могут быть конвертированы в docID целыми партиями при помощи массового сравнения с этим файлом.
Этот метод используется преобразователем URL для конвертирования URL-адресов в docID. Данный режим пакетного обновления очень важен, поскольку без него пришлось бы проводить индивидуальный поиск по диску для каждой из 322 миллионов ссылок в нашем наборе данных, что отняло бы больше месяца.

4.2.4 Лексикон

Словарь имеет несколько различных форм.
Одним из важных отличий от прошлых систем является то, что словарь может без особых затрат быть помещён в память. В текущей реализации возможно размещать лексикон в 256 МБ оперативной памяти. Нынешний словарь содержит
14 миллионов слов (хотя некоторые редкие слова не были добавлены в него). Он
выполнен в двух частях – список слов (объединённых вместе, но разделенных
нулями) и хэш-таблица указателей. Список слов несёт определённую вспомогательную информацию для некоторых функций, детальный разбор которых выходит за рамки данной работы.

4.2.5 Хитлисты (Hit Lists)

Хитлист соответствует
списку вхождений определенного слова в конкретном документе, включая
информацию о положении, шрифте и регистре (hit, англ. – удар, попадание, hit list букв. – список попаданий слова в документ, прим. пер.). Хитлист занимает большую часть дискового пространства, используемого прямым и инверсированным индексами. В связи с этим, важно записывать выборку хитов настолько эффективно, насколько это возможно. Мы рассмотрели несколько
вариантов кодирования положения, шрифта и регистра: простое кодирование
(тройка целочисленных значений), компактное кодирование (оптимизация распределения
битов вручную) и кодирование Хаффмана. В конце концов, мы выбрали компактное
кодирование, поскольку оно требует намного меньше места, чем простое
кодирование и требует гораздо меньше работы с битами, чем кодирование
Хаффмана. Элементы хитов показаны на рисунке 3.

Рисунок 3. Прямой и обратные
индексы и словарь.

Рисунок 3. Прямой и обратный индексы и словарь.

Наше компактное кодирование использует
два байта для каждого хита.
Существуют два типа хитов:
сложные (fancy) и простые (plain). Сложные включают в себя хиты, которые встречаются в URL, названии, ссылочном анкоре или мета-теге. Простые включают всё остальное. Простой хит состоит
из бита регистра, размера шрифта и 12 бит положения слова в документе (все
позиции выше, чем 4095 помечаются как 4096). Размер шрифта записывается по
отношению к остальной части документа с использованием трех битов (всего фактически
используется семь значений, потому что 111 является признаком сложного хита). Сложный хит состоит из бита регистра, размера
шрифта больше 7, что указывает на его сложность, 4 битов для кодирования типа сложного
хита,
и 8 бит положения. Для хита ссылки (anchor hit),
8 бит позиции разделены на 4 бита положения ссылки и 4 бита для хэша docID, где
встречается ссылка. Это даёт нам некоторое ограничение поиска по длине фразы.
Мы собираемся обновить способ хранения хитов анкора, чтобы обеспечить запись более точных данных о позиции и docIDhash. Мы используем отношение размера шрифта к остальной части документа, поскольку при поиске нежелательно по-иному ранжировать идентичные документы, различающиеся только шрифтом.

Длина хитлиста записывается до самого хита.
Для экономии места размер хитлиста комбинируется с wordID в прямом индексе и docID в обратном индексе. Это ограничивает размеры записи до
8 и 5 битов соответственно (существуют несколько методов, которые позволяют заимствовать
8 битов из wordID). Если длина хитлиста превышает лимит записи на несколько бит, то вместо неё записывается код выхода, а последующие два байта содержат фактический размер.

4.2.6 Прямой индекс

Прямой индекс фактически уже частично
отсортирован. Он хранится в нескольких бочках (мы использовали 64). Каждая
бочка хранит в себе диапазон wordID. Если документ содержит слова, которые попадают в определённую бочку, то его docID записывается в бочку перед списком wordID с хитлистами, которые
соответствуют этим словам. Эта схема требует немного больше места для хранения из-за дубликатов docID, но разница настолько невелика, что не создаёт проблем даже с крупным количеством ячеек. Данная схема экономит много времени и позволяет обойти трудности программирования заключительной фазы индексации, выполняемой сортировщиком. Более того, вместо записи фактического wordID, мы сохраняем каждый wordID в виде относительной разности с минимальным wordID, попавшим в бочку. Таким образом, мы можем
использовать всего 24 бита для тех wordID, которые находятся в несортированных бочках,
оставляя 8 бит для записи длины хитлиста.

4.2.7 Инвертированный индекс

Инвертированный (обратный) индекс состоит из тех же бочек, что и прямой индекс, но с одним отличием: бочки уже были обработаны сортировщиком.
Для каждого корректного wordID,
лексикон содержит указатель на бочку, в которую попадает этот wordID. Он указывает на доклист, т.е. список docID вместе с их соответствующими хитлистами.
Этот доклист отображает все вхождения данного слова во всех
документах.

Важным является вопрос, в каком порядке docID должны быть записаны в доклисте. Проще всего хранить их сортированными по docID. Это позволяет быстро объединять различные доклисты для запросов, состоящих из нескольких слов. Другим вариантом хранения является ранжирование по частоте появления
слова в каждом документе. Такой способ значительно упрощает ответы на однословные запросы, а так же повышает вероятность, что ответы на многословные запросы будут располагаться ближе к началу. Однако в этом случае весьма затрудняется объединение доклистов. Кроме того, это
осложняет разработку тем, что изменение функции ранжирования требует
перестроения индекса. Мы нашли компромисс между обоими вариантами, сохраняя два набора инверсированных бочек – один набор для хитлистов, которые включают title документа или анкорные хиты, а другой набор для всех хитлистов.
Таким образом, сначала мы проверяем первый набор бочек и если достаточного
количества совпадений в этих бочках нет, то мы начинаем проверку более крупных бочек.

4.3 Веб-сканирование

Обеспечение стабильной работы веб-сканера является весьма трудным процессом. В это задаче встают не только проблемы производительности и надёжности, но и, что более важно, сказывается человеческий фактор. Система сканирования является самой уязвиой, так как ей приходится взаимодействовать с сотнями и тысячами веб-серверов и DNS вне её непосредственного контроля.

В целях масштабирования сотен миллионов
веб-страниц, Google обладает быстрой распределённой системой сканирования. Одиночный URL-сервер составляет списки URL-адресов для нескольких сканеров (чаще всео мы использовали 3 краулера). URL-сервер и сканеры были разработаны на языке программирования Python. Каждый сканер одновременно обслуживает около 300 открытых соединений. Это требуется для достаточно быстрого получения веб-страниц из Интернета. На максимальной скорости система способна сканировать более 100 веб-страниц за одну секунду с использованием четырёх сканеров. Таким образом, генерируется порядка 600 Кб данных каждую секунду. Основной нагрузкой на систему является поиск DNS.
Каждый сканер оснащён индивидуальным кэшем (промежуточным буфером быстрого доступа) для хранения DNS, так что ему не требуется заново искать DNS перед сканированием каждого документа. Каждое из сотен соединений
может находиться в разных состояниях: поиск DNS, подключение к хосту,
отправка запроса, получение ответа. Из-за этих факторов сканер является весьма сложным компонентом системы. Краулер работает с асинхронным вводом/выводом данных, чтобы управлять событиями, и использует несколько очередей для изменения состояния выбранных страниц.

Оказывается, что обеспечение работы сканера,
который подключается к более чем 500,000 серверов и генерирует десятки миллионов записей в логах, вызывает множество телефонных звонков и электронных писем. Из-за огромного числа пользователей в онлайне, всегда находятся те, кто не знает о сканерах, так как встречаются с ним впервые. Практически ежедневно нам присылают письма вида: «Ого, вы просмотрели очень много страниц на моём сайте. Он вам понравился?» Также существуют пользователи, которые не знают о протоколе запрета индексации, и считают, что достаточной защитой от
индексации является текст вида «Эта страница защищена авторским правом и не
должна индексироваться», что, само собой разумеется, сканер не может понять. Кроме того, из-за огромного объёма обрабатываемых данных, встречаются непредвиденные ситуации. К примеру, однажды наша система пыталась просканировать многопользовательскую онлайн-игру.
Это привело к тому, что в чате игры появилось множество бессмысленных сообщений! Как оказалось, эту проблему было легко решить.
Однако она не возникала до тех пор, пока мы не скачали десятки миллионов страниц. В
связи с огромным разнообразием веб-страниц и серверов, практически невозможно
протестировать работу сканера, не запуская его на большую часть Интернета. Неизменно присутствуют сотни скрытых проблем, которые могут всплыть, к примеру, только на одной
странице из всего Интернета и нарушить работу сканера, или ещё хуже,
спровоцировать к непредсказуемое или неверное поведение. Системы, работаютщие с большими частями Интернета, должны разрабатываться с высоким уровнем надёжности и тщательно проверяться. Из-за того, что крупные сложные системы наподобие сканеров,
будут неизменно вызывать проблемы, следует выделить существенное количество ресурсов для чтения электронной почты и решения этих проблем по мере их
появления.

4.4 Индексация Веба

Парсинг. Любой парсер, предназначенный для работы во всей Сети, должен сопровождаться огромным массивом возможных ошибок.
Они варьируются от опечаток в HTML-тегах
до килобайтов нулей в середине тега, символов вне таблицы ASCII, HTML
тегов с сотнями вложений и великим множеством других ошибок, которые только
можно представить. Для достижения максимальной скорости, вместо использования YACC (стандартный генератор синтаксических анализаторов в Unix-системах) для
создания CFG-парсера (Context-Free Grammar, парсер контекстно-свободной грамматики), мы используем flex (Fast Lexical Analyzer, не путать c Flex SDK) для создания лексического
анализатора, который мы комплектуем его собственным протоколом. Для разработки этого точного и достаточно быстрого парсера, нам пришлось приложить немало усилий.

Индексирование
документов в бочки
. После того, как каждый документ проанализирован парсером, он зашифровывается в несколько бочек. Каждое слово преобразуется в wordID с
помощью хэш-таблицы внутри памяти – лексикона. Обновления хэш-таблицы лексикона записываются в файл лога. После преобразования слов в wordID, число их вхождений в текущем документе переводится в хитлисты и записывается в прямую бочку. Основной трудностью с распараллеливанием стадии индексации
является то, что лексикон должен быть общедоступен. Вместо разрешения одновременного доступа к словарю, мы решили записывать лог всех дополнительных слов вне 14 млн слов в базе лексикона, которую мы решили не изменять. Таким образом, несколько
индексаторов могут работать параллельно, а затем небольшой лог-файл дополнительных слов
может быть обработан одним итоговым индексатором.

Упорядочивание. Для создания инвертированного индекса, сортировщик упорядочивает каждую прямую бочку
по wordID и создает инвертированную бочку для title документа и анкорных хитов и полного текста, а так же  инвертированную бочку с полным текстом.
Этот процесс происходит с одной бочкой за раз и требует небольшого временного пространства на диске. К тому же, мы распараллеливаем стадию сортировки и используем
максимальное количество доступных компьютеров, просто запуская несколько сортировщиков, которые
могут обрабатывать различные блоки в одно и то же время. Поскольку бочки не помещаются в оперативную память целиком, сортировщик дополнительно разбивает их на подходящие по объёму корзины, формируемые по wordID и docID. Затем сортировщик загружает каждую
корзину в память, сортирует её и  записывает её содержимое в малую (сокращённую) инвертированную бочку и полную инвертированную бочку.

4.5 Процесс поиска

Задачей поискового процесса является эффективность обеспечения качественных результатов. Многие крупные коммерческие поисковые системы уже далеко продвинулись в плане эффективности. Именно поэтому в нашем исследовании мы сконцентрировались на повышении качества поиска, хоть мы и считаем, что наша разработка сможет функционировать в промышленных масштабах после незначительных модификаций. Процесс обработки запроса Google показан на рисунке 4.

Рисунок 4. Обработка запроса в Google.

Рисунок 4. Обработка запроса в Google.

4.5.1 Система ранжирования

Google хранит намного больше
информации о веб-документах, по сравнению с обычными поисковыми системами. Каждый хитлист
включает в себя информацию о позиции слова, его шрифте и регистре. К тому же, мы учитываем хиты из анкоров ссылок и PageRank документа. Объединить все эти данные в одну оценку нелегко. Мы спроектировали функцию ранжирования таким образом, что ни один фактор по отдельности не способен оказывать дисгармоничное влияние на итоговую оценку. Сперва рассмотрим простейший
случай – запрос, состоящий только из одного слова. Для того чтобы ранжировать документ
по однословному запросу, Google просматривает хитлист
документа по данному слову. Google рассматривает каждый хит, как принадлежащий к нескольким типам (title, анкор, URL, текст с крупным
и мелким шрифтами, и т.д.), каждый из которых имеет свой собственный вес типа (type-weight). Типовые веса образовывают индексированный по типу вектор. Google подсчитывает количество
хитов каждого типа в хитлисте. Затем каждый подсчёт преобразовывается в вес подсчёта (count-weight). Вес подсчёта поначалу линейно возрастает с каждым подсчётом, но затем скорость возрастания резко падает, так что превышение определённого количества вхождений уже не оказывать влияние. Возьмём скалярное произведение вектора весов подсчёта и вектора типовых весов для вычисления IR-оценки документа (Information Retrieval Score, численная оценка релевантности документа). И, наконец, IR-оценка комбинируется с PageRank для назначения итогового ранга документа.

Для запроса, состоящего из нескольких
слов, ситуация более сложная. В таких условиях несколько хитлистов должны быть просканированы одновременно и при этом хиты, расположенные ближе друг к другу в документе, взвешивались выше хитов, расположенных на отдалении. Хиты из нескольких хитлистов подобраны таким образом, чтобы соседние хиты совпадали
друг с другом. Для каждого совпавшего набора хитов вычисляется
аппроксимация. Аппроксимация основана на том, как далеко находятся друг от
друга встречаются хиты в документе (или анкоре ссылки), и подразделяется на 10 «зон» с разными значениями,
начиная от полного совпадения фразы до «даже близко не стоят». Величины вычисляются
не просто для каждого типа хитов,
а для каждого типа хитов и аппроксимации. Каждая пара типа и аппроксимации имеет вес типа-аппроксимации (type-prox-weight). Величины преобразуются в
вес подсчёта и далее рассчитывается скалярное произведение веса подсчёта и веса типа-аппроксимации для вычисления IR-оценки.
Все эти числа и матрицы могут отображаться в результатах поиска в специальном режиме отладки. Наглядное отображение величин было очень полезно в разработке системы
ранжирования.

4.5.2 Обратная связь

Функция ранжирования имеет много
параметров, таких как типовой вес и вес типа-аппроксимации. Определение корректности значений этих параметров сродни чёрной магии. Для того чтобы сделать это,
у нас есть система пользовательской обратной связи в поисковой системе. Доверенный
пользователь может по желанию оценивать все полученные результаты. Его обратная связь сохраняется. В будущем, после модификации функции ранжирования, мы сможем увидеть влияние обновления на все предыдущие поисковые сеансы, результаты которых оценивал человек. И хотя это не является идеальным способом проверки, такой способ даёт нам примерное отображение эффекта изменения функции на поисковые результаты.

5
Результаты работы

Наиболее важная характеристика поисковой системы
– это качество результатов поиска. Хотя полная оценка пользователями не
является предметом исследования этой статьи, опыт работы с Google показал,
что по большинству запросов он выдаёт лучшие результаты, чем крупные
коммерческие поисковые системы. В качестве примера, который иллюстрирует
использование PageRank, анкоров ссылок и аппроксимацию, на рисунке 5 показаны результаты
Google по запросу «Билл Клинтон». Эти результаты демонстрирует
некоторые особенности Google. Результаты кластеризованы по серверу. Это значительно помогает при анализе выдачи. Часть результатов, как и следовало ожидать, относится к домену whitehouse.gov. В настоящее время большинство крупных
коммерческих поисковых систем не просто не выдают верных результатов с whitehouse.god, более того, результатов вообще нет. Обратите внимание, что у первого результата отсутствует title. Это произошло по той причине, что страница не была просканирована. Вместо этого Google
полагался на текст анкора для определения релевантности ответа запросу. Аналогично, пятым результатом является адрес электронной
почты, который, конечно, невозможно просканировать. Этот результат так же обусловлен текстом анкора.

Рисунок 5. Примеры результатов поиска
в Google.

Рисунок 5. Примеры результатов поиска Google.

Все результаты являются страницами
достаточно высокого качества и при последней проверке ни одна из них не являлась битой. В значительной степени это обусловлено высоким PageRank всех результатов. На рисунке 5 PageRank
отображён в процентах (числом и графической полоской). Наконец, в выдаче нет результатов о каких-либо других Биллах, кроме Клинтона или о прочих Клинтонах, при этом не Биллах. Причиной этому служит заданная нами высокая важность аппроксимации расположения слов. Конечно же,
настоящая проверка качества поисковой системы будет включать обширное исследование пользователей или анализ результатов, выходящий за рамки данной работы.
Вместо этого, мы приглашаем читателей опробовать Google лично по адресу google.stanford.edu.

5.1 Требуемый объём памяти

Помимо качества поиска, Google
спроектирован для экономически эффективного масштабирования наряду с ростом Веба.
Одним из аспектов этой проблемы является эффективное использование дискового пространства. В таблице
1 представлена некоторая статистика и требуемый объём хранения данных Google. По причине сжатия, общий объём хранилища составляет 53 Гб, немногим более одной трети от всего объёма записанных данных. В условиях современных цен на дисковые накопители хранилище Google является относительно дешёвым источником полезных данных. Что более важно, суммарно, все данные, используемые поисковой системой, занимают сопоставимый объём накопителя – около 55 Гб. Более того, большинство запросов могут быть обработаны с использованием только малого инвертированного индекса. В условиях улучшенного шифрования и сжатия индекса документов, высококачественная поисковая система может быть размещена на новом ПК с жёстким диском объёмом 7 Гб.

5.2 Производительность системы

Для поисковой системы важно эффективно сканировать и индексировать документы. Это обеспечивает сохранение информации в
актуальном состоянии и высокую скорость тестирования крупных обновлений системы. Для Google основными операциями являются сканирование, индексирование и упорядочивание данных. Сегодня трудно
определить общее время сканирования из-за того, что периодически переполнялись жёсткие диски, падали DNS-сервера или система была остановлена по ряду других причин. В общей
сложности потребовалось около 9 дней, чтобы скачать 26 миллионов страниц
(включая ошибки). Однако как только система заработала стабильно, загрузка страниц пошла
гораздо быстрее – 11 миллионов страниц было скачано всего за 63 часа, т.е. в среднем чуть более 4
млн. страниц в день или 48,5 страниц в секунду. Мы включили индексатор и сканер
одновременно. Индексатор работал быстрее сканеров, так как мы уделили много времени его оптимизации, чтобы обеспечить быструю работу системы. Оптимизация индексатора включала в себя масштабные обновления индекса документов и размещение жизненно необходимых структур данных на локальном жёстком диске. Как итог, индексатор обрабатывает около 54 страниц в секунду. Сортировщики могут польностью работать параллельно: при использовании 4 компьютеров, весь процесс сортировки
занимает около 24 часов.

Таблица 1. Статистические данные.

Статистические данные памяти Статистические данные веб-страниц
Общий размер выбранных страниц 147, 8 Гб Количество выбранных страниц 24 мил.
Сжатие хранилища 53,5 Гб Количество видимых ссылок 76,5 мил.
Короткий обратный индекс 4,1 Гб Количество адресов e-mail 1,7 мил.
Полный обратный индекс 37,2 Гб Количество ошибок 404 1,6 мил.
Словарь 293 Мб    
Временные данные ссылок (не общие) 6,6 Гб    
Индекс документов, включая различные шины данных 9,7 Гб    
Связь базы данных 3,9 Гб    
Всего без хранилища 55,2 Гб    
Всего с хранилищем 108,7 Гб    

5.3 Производительность поиска

Улучшение производительности поиска не было
основным направлением наших исследований до этого момента. Текущая версия Google отвечает на большинство запросов за диапазон от 1 до 10 секунд. Это время, главным образом, тратится на передачу команд ввода/вывода диску по NFS (Network File System), протоколу сетевого доступа к файловым системам (так как диски расположены на нескольких машинах). К тому же, Google ещё не оснащён такими оптимизациями, как кэширование запросов, подиндексы часто используемых слов, и прочими общими оптимизациями. Мы намерены значительно увеличить скорость работы Google с помощью распределения и улучшения оборудования, программного обеспечения и модификации алгоритмов. Нашей целью является способность обработки несколько сотен запросов в секунду. Таблица 2 содержит примеры
интервалов обработки запроса по сравнению с текущей версией Google. Они повторяются, чтобы
показать увеличение скорости работы с кэшированным IO.

Таблица 2. Время поиска.

Запрос Начальный запрос Повтор того же запроса (в основном кэшированной IO)
Процессорное время Общее время Процессорное время Общее время
Альберт Гор 0,09 2,13 0,06 0,06
Вице-президент 1,77 3,84 1,66 1,80
Жесткий диск 0,25 4,86 0,20 0,24
Поисковые машины 1,31 9,63 1,16 1,16

6 Заключение

Google спроектирована как масштабируемая поисковая система. Её основная цель заключается в обеспечении высокого качества
результатов поиска по быстро растущей Всемирной Сети. Google использует несколько методик для улучшения качества поиска, включая PageRank, ссылочные анкоры и значения аппроксимации. На сегодняшний день Google является полноценной программной архитектурой для сбора
веб-страниц, их индексации и выполнения по ним поисковых запросов.

6.1 Дальнейшая работа

Крупномасштабная система информационного поиска представляет собой весьма сложное программное обеспечение, стоящее в самом начале своего развития. Нашей ближайшей задачей является улучшение эффективности поиска и масштабирование системы до 100 млн веб-страниц. Несколькими простыми улучшениями эффективности являются кэширование запросов, рационально распределение дисков и подиндексы. Следующим пунктом разработки является обновление данных. Нам необходимы качественные алгоритмы, определяющие какие из старых страниц должны быть просканированы заново и какие из новые должны быть просканированы впервые. Исследование в этом
направлении проводилось [Чо 98]. Одним из перспективных направлений
исследований является использование функции кэширования на прокси-серверах для создания поисковых баз
данных, работающих по необходимости. Мы планируем добавить простые функции,
поддерживаемые коммерческими поисковыми системами: логические операторы,
отрицание и стемматизацию. Тем не менее, положено начало исследованию и других функций, таких как обратная связь о релевантности и кластеризация (на данный момент Google поддерживает простую кластеризацию по имени хоста). Мы планируем
внедрить пользовательский контекст (например, учёт геолокации пользователя) и обобщение
результатов. Мы также работаем над расширением использования ссылочной
структуры и анкора ссылки. Простые опыты показывают, что PageRank может быть персонализирован за счёт увеличения веса домашней страницы или закладок пользователя.
Что касается ссылочных анкоров, то мы проводим опыты по использованию текста, окружающего ссылки, в дополнение к анализу непосредственно анкора. Система веб-поиска является весьма обширной темой для научно-исследовательской работы. У нас есть множество идей для реализации, поэтому не стоит ожидать сокращение данного раздела в ближайшем будущем.

6.2 Высококачественный поиск

Самой большой проблемой, стоящей перед пользователями поисковых систем сегодня, является качество полученных
результатов. Хотя зачастую результаты бывают забавными и расширяют кругозор пользователей, они могут так же и разочаровывать и тратить драгоценное время. Например, первым ответом по запросу «Билл Клинтон» в одной из самых популярных
коммерческих поисковых систем была шутка дня Билла Клинтона 14 апреля 1997
года. Google предназначен для постоянного обеспечения более высокого качества поиска, чтобы по мере роста Веба информацию можно было легко найти. Для
достижения этой цели Google активно использует гипертекстовую информацию,
включающую в себя ссылочную структуру и анкоры ссылок. Google также использует аппроксимацию и информацию о шрифтах. Несмотря на то, что сегодня сложно оценить качество работы поисковой системы, мы субъективно оцениваем Google выше, сравнивая его результаты с современными коммерческими поисковыми системами. Анализ ссылочной структуры с помощью
Google PageRank позволяет оценить качество веб-страниц. Восприятие анкора ссылки в качестве описания указанного документа повышает релевантность (и, в какой-то степени, качество) поисковых результатов. Использование данных об аппроксимации так же помогает повысить релевантность результатов для многих
запросов.

6.3 Масштабируемая архитектура

Помимо качества поиска, Google
предназначена для масштабирования. Она должна быть эффективной как в пространстве, так и во времени, а неизменные величины имеют решающее значение при работе со всем Вебом. При разработке Google мы выявили «слабые звенья» в работе центрального процессора, доступе к памяти, объёме памяти, работе дисков, пропускной способности и ёмкости диска, а так же задержке передачи данных по сети. Google развивался и укреплял критически важные части системы. Основные
структуры данных Google рационально используют доступное дисковое пространство. При этом, операции сканирования, индексации и сортировки достаточно эффективны,
чтобы построить индекс для значительной части Веба – 24 млн страниц, менее
чем за одну неделю. Мы предполагаем, что будет возможно создание индекса из 100 млн веб-страниц менее чем за месяц.

6.4 Инструмент исследования

Google
является
не только высококачественной поисковой системой, но и инструментом исследования.
Данные, собранные Google
уже отражены во многих работах, представленных на различных конференциях. Недавние исследования, такие как [Abiteboul 97], продемонстрировали ряд
ограничений по запросам об Интернете, ответы на которые можно получить, не имея местного доступа к Сети. Это означает, что Google (или аналогичная система) как инструмент исследование не только ценен, но ещё и необходим в широком спектре применений.
Мы надеемся, что Google
станет ресурсом для пользователей и исследователей по всему миру и искрой следующего поколения технологий поисковых систем.

7 Благодарности

Скотт Хассан и Алан Стеремберг критически оценивали разработку Google. Их талантливый вклад незаменим, и авторы им очень благодарны.
Мы также хотели бы поблагодарить Гектора Гарсиа-Молину, Раджива Мотуани, Джеффа
Ульмана, Терри Винограда и весь коллектив WebBase за их поддержку и
плодотворную дискуссию. Наконец, мы хотели бы выразить признательность за щедрую поддержку оборудованием компаниям IBM, Intel и Sun и другим нашим спонсорам. Описанное здесь исследование проводилось в рамках Stanford Integrated Digital Library Project при поддержке
Национального научного фонда под соглашением о сотрудничестве IRI-9411306.
Финансирование данного соглашения о сотрудничестве также обеспечивается Агентством
по перспективным оборонным научно-исследовательским разработкам США, НАСА, корпорацией
Interval Research и промышленными партнерами проекта Stanford Digital Libraries Project.

Литература

  • Best
    of the Web 1994 — Navigators botw.org/1994/awards/navigators.html
  • Bill
    Clinton Joke of the Day: April 14, 1997. io.com/~cjburke/clinton/970414.htm l.
  • Bzip2
    Homepage muraroa.demon.co.uk/
  • Google
    Search Engine google.stanford.edu/
  • Harvest
    harvest.transarc.com/
  • Mauldin,
    Michael L. Lycos Design Choices in an Internet Search Service, IEEE Expert
    Interview computer.org/pubs/expert/1997/trends/x1008/mauldin.htm
  • The
    Effect of Cellular Phone Use Upon Driver Attention webfirst.com/aaa/text/cell/cell0toc.htm
  • Search
    Engine Watch searchenginewatch.com/
  • RFC
    1950 (zlib) ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html
  • Robots
    Exclusion Protocol: info.webcrawler.com/mak/projects/robots/exclusion.htm
  • Web
    Growth Summary: mit.edu/people/mkgray/net/web-growth-summary.html
  • Yahoo!
    yahoo.com/
  • [Abiteboul
    97] Serge Abiteboul and Victor Vianu, Queries and Computation on the Web.
    Proceedings of the International Conference on Database Theory. Delphi, Greece 1997.
  • [Bagdikian 97]
    Ben H. Bagdikian. The Media
    Monopoly. 5th Edition. Publisher: Beacon, ISBN:
    0807061557
  • [Cho
    98] Junghoo Cho, Hector Garcia-Molina, Lawrence
    Page. Efficient Crawling Through URL Ordering. Seventh International Web
    Conference (WWW 98). Brisbane,
    Australia,
    April 14-18, 1998.
  • [Gravano
    94] Luis Gravano, Hector Garcia-Molina, and A. Tomasic. The Effectiveness of
    GlOSS for the Text-Database Discovery Problem. Proc. of the 1994 ACM SIGMOD
    International Conference On Management Of Data, 1994.
  • [Kleinberg
    98] Jon Kleinberg, Authoritative Sources in a Hyperlinked Environment, Proc.
    ACM-SIAM Symposium on
    Discrete Algorithms, 1998
    .
  • [Marchiori
    97] Massimo Marchiori. The Quest for Correct Information on the Web: Hyper
    Search Engines. The Sixth International WWW Conference (WWW 97). Santa Clara, USA, April 7-11,
    1997.
  • [McBryan 94]
    Oliver A. McBryan. GENVL and
    WWWW: Tools for Taming the Web. First International Conference on the World
    Wide Web. CERN, Geneva (Switzerland),
    May 25-26-27 1994. cs.colorado.edu/home/mcbryan/mypapers/www94.ps
  • [Page
    98] Lawrence
    Page, Sergey Brin, Rajeev Motwani, Terry Winograd. The PageRank Citation
    Ranking: Bringing Order to the Web. Manuscript in progress. google.stanford.edu/~backrub/pageranksub.p
    s
  • [Pinkerton
    94] Brian Pinkerton, Finding What People Want: Experiences with the WebCrawler.
    The Second International WWW Conference Chicago,
    USA, October
    17-20, 1994. info.webcrawler.com/bp/WWW94.html
  • [Spertus
    97] Ellen Spertus. ParaSite: Mining Structural Information on the Web. The
    Sixth International WWW Conference (WWW 97). Santa Clara, USA, April 7-11, 1997.
  • [TREC
    96] Proceedings of the fifth Text REtrieval Conference (TREC-5). Gaithersburg, Maryland,
    November 20-22, 1996. Publisher: Department of Commerce, National Institute of
    Standards and Technology. Editors: D. K. Harman and E. M. Voorhees. Full text
    at: trec.nist.gov/
  • [Witten 94] Ian H Witten,
    Alistair Moffat, and Timothy C. Bell. Managing Gigabytes: Compressing and
    Indexing Documents and Images. New
    York: Van Nostrand Reinhold, 1994.
  • [Weiss
    96] Ron Weiss, Bienvenido Velez, Mark A. Sheldon, Chanathip Manprempre, Peter Szilagyi,
    Andrzej Duda, and David K. Gifford. HyPursuit: A Hierarchical Network Search
    Engine that Exploits Content-Link Hypertext Clustering. Proceedings of the 7th
    ACM Conference on Hypertext. New York,
    1996.

Краткая биография

Фотография Сергея Брина.

Сергей Брин получил степень бакалавра в
области математики и компьютерных наук в Мэрилендском университете в
Колледж-Парке в 1993 году. На момент публикации он является кандидатом компьютерных
наук в Стэнфордском университете, где он получил степень магистра в 1995 году.
Он является лауреатом стипендии Национального научного фонда. Его научные
интересы включают поисковые системы, извлечение информации из несистематизированных
источников и дата-майнинг больших наборов текста и научной информации.

Фотография Лоуренса Пейджа.

Лоуренс Пейдж родился в Ист-Лансинге,
штат Мичиган, и получил степень бакалавра в области вычислительной техники в Мичиганском
Университете в 1995 году. В настоящее время является кандидатом наук в области
компьютерных наук в Стэнфордском университете. Среди его научных
интересов ссылочная структура Сети, человеко-компьютерное взаимодействие, поисковые системы, масштабируемость интерфейсов доступа к
информации и дата-майнинг персональных сведений.

8 Приложение A: реклама и смешанные мотивы

В настоящее время доминирующей бизнес-моделью
для коммерческих поисковых систем является реклама. Цели рекламной
бизнес-модели не всегда соответствуют обеспечению качественного поиска для пользователей.
Например, в прототипе нашей поисковой системе одним из первых результатов для запроса «мобильный телефон» является «Влияние использования мобильного телефона на внимание
водителей», исследование, которое очень подробно описывает отвлекающий фактор и
риск, связанный с разговором по мобильному телефону во время вождения. Этот
результат был выдан первым из-за своей высокой важности, вычисленной алгоритмом PageRank, аппроксимацией
важности цитирования в Интернете [Page 98]. Очевидно, что коммерческая поисковая система, которая рекламирует мобильные телефоны, столкнётся с трудностями при оценке важности документа, который наша система выдала своим платёжеспособным рекламодателям. По этой причине и опыту [Bagdikian 83], мы предполагаем, что
поисковые системы, финансируемые рекламодателями, будут изначально предвзяты к ним
и не будут учитывать нужды потребителей.

Так как оценка поисковых систем очень
сложна даже для экспертов, предвзятость поисковой системы является критически важной.
Наглядным примером была OpenText,
которая, как сообщалось, продавала компаниям позиции их сайтов в топе поисковых результатов по целевым запросам [Marchiori 97]. Данный вид «предвзятости» гораздо более опасен, чем реклама, посколько совершенно неясно, кто
«заслуживает» топовых результатов, а кто готов просто платить
деньги. Эта бизнес-модель получила резко негативную оценку и OpenText перестала считаться жизнеспособной поисковой системой. Но менее явная предвзятость, вероятно, будет допускаться на
рынок. Например, поисковая система может добавить небольшие позитивные факторы ранжирования результатам для «дружественных» компаний, и негативные факторы – конкурентам. Этот тип предвзятости очень трудно
обнаружить, но он все ещё может оказывать значительное влияние на рынок. Кроме
того, доходы от рекламы часто дают стимул обеспечивать плохие результаты
качества поиска. Например, мы заметили, что основные поисковые системы не выдают домашнюю страницу одной крупной авиакомпании, если ввести её название в качестве запроса.
Оказалось, что авиакомпания закупила дорогостоящие объявления на своё имя в качестве поискового запроса. Лучшая поисковая система не выдавала бы это
объявление, и, возможно, не получала бы доходов за рекламу от
авиакомпании. В общем, можно утверждать, с потребительской точки зрения, что
чем качественней система информационного поиска, тем меньший объем рекламы тех
организаций, который заинтересованы в продвижении
сайтов
или своих продуктов, будет представлено для потребителей её поиска,
желающего найти то, что они хотят. Это, конечно, подрывает бизнес-модель
существующих поисковых систем, которые обеспечивают себя рекламой. Тем не менее,
всегда будут приходить деньги от рекламодателей, которые хотят «протолкнуть» свой товар, в особенности, новинки. Но мы считаем, что вопрос о
рекламе вызывает достаточно разнообразных стимулов, которые должны быть у поисковой системы со здоровой конкуренцией, которая прозрачна в своей работе и научной сфере.

9 Приложение Б: Масштабируемость

9.1 Масштабируемость Google

Мы разработали Google для
масштабирования в ближайшее время до 100 миллионов веб-страниц. Мы только что получили
дисковый накопитель и компьютеры для обработки такого количества документов. Все трудоемкие части системы
распараллеливаются и масштабируются практически линейно. Они включают в себя
такие вещи, как сканеры, индексаторы и сортировщики. Мы также считаем, что
большая часть структур данных будет заметно расширяться. Тем не менее, на 100
миллионах веб-страниц мы будем очень близки ко множеству ограничений в распространённых операционных
системах (в настоящее время мы работаем на Solaris и Linux). Это включает в себя проблемы адресной памяти, числа открытых файловых дескрипторов, сетевых гнёзд,
пропускной способности и многого другого. Мы считаем, что расширение к более чем
100 миллионам страниц значительно увеличит сложность нашей системы.

9.2 Масштабируемость централизованных индексирующих архитектур

Поскольку возможности компьютеров
возрастают, становится возможным индексирование очень большого количества текста с умеренными затратами. Конечно, так требовательные к пропускной способности канала данные, как видео, вероятно, станут более распространены. Но, так как затраты
на производство текста низки по сравнению с медиа, к примеру, видео, текст,
вероятно, останется самым распространённым типом данных в Сети. Кроме того, вполне вероятно, что
скоро нам будет доступно распознавание речи, что делает целесообразную работу
преобразования речи в текст, расширяя количество доступного текста. Все это создаёт
удивительные возможности для централизованной индексации. Вот наглядный
пример. Предположим, что мы хотим индексировать всё и всеми написанное в США
в течение года. Предполагается, что в США проживает 250 миллионов человек и они
пишут в среднем 10 кб в день. Это составляет около 850 терабайт. Также
предположим, что индексация терабайта может быть выполнена сейчас с умеренными
затратами. Мы также предполагаем, что методы индексации, используемые для
текста, линейны или почти линейны по своей сложности. Учитывая все эти
предположения, можно вычислить, сколько времени потребуется для индексации 850 терабайтов с умеренными затратами, предполагая
определенные факторы развития. Закон Мура был определен в 1965 году как удвоение
производительности процессора каждые 18 месяцев. Это оказалось справедливо не
только для процессоров, но и для других важных составляющих системы, таких как жёсткие диски. Если предположить, что закон Мура будет действовать и в дальнейшем, нам потребуется всего 10 удвоений, или 15 лет, чтобы достичь нашей – цели индексации всего и всеми
написанного в США в течение года с затратами, которые бы могли себе позволить
небольшие компании. Конечно, специалисты технического обеспечения, имеющие дело
с законом Мура, не уверен, что он будет работать ещё 15 лет, но, несомненно, по-прежнему существует много интересных применений этого закона в различных сферах информационных технологий.

Конечно распределенные системы, такие
как Gloss
[Gravano 94] или Harvest, зачастую будут являться наиболее эффективным и элегантным
техническим решением индексации, но, кажется, будет трудно убедить мир использовать эти системы по причине высоких административных издержек на настройку большого количества таких установок. Конечно, вполне вероятно резкое
снижение административных расходов на такие системы. Если это произойдет, и все начнут
работать с системой распределённой индексаци, поиск, безусловно, резко
улучшится.

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

Перевод материала «The Anatomy of a Large-scale Hypertextual Web Search Engine» выполнили