Google может считать PageRank впятеро быстрее

Ученые из Стэнфордского университета опубликовали работу о том, как придать поисковой машине Google гигантское ускорение.

Пользователи любят поисковую машину Google за ее быстроту, но команда из Стэнфорда предложила способ сделать ее еще в пять раз быстрее. При таком запасе быстродействия Google можно будет настраивать индивидуально для каждого пользователя. Например, спортивному болельщику по ключевому слову tiger будут выпадать страницы не о крупной азиатской кошке, а об игроке в гольф Тайджере Вудсе.

Сейчас система ранжирования Google использует метод PageRank, изобретение соучредителя компании Ларри Пейджа. Этот алгоритм определяет популярность и релевантность веб-сайтов по тому, как часто на них ссылаются другие сайты. «Вычисление PageRank для миллиарда веб-страниц может занять несколько дней. Сейчас Google ранжирует и разыскивает три миллиарда веб-страниц, и для каждого персонализированного или тематического ранжирования требуются отдельные многодневные расчеты», — говорится в заявлении университета.

Чтобы ускорить работу PageRank, стэнфордские ученые разработали три метода, основанных на линейной алгебре. Эти методы описаны в трех работах, представленных на Двенадцатой ежегодной конференции по World Wide Web в Будапеште (Венгрия).

• Первый метод, BlockRank, дает самое значительное — трехкратное — ускорение PageRank. В нем используется сделанное учеными открытие: на большинстве сайтов до 80% ссылок указывают на другие страницы того же сайта, так что каждый сайт похож на толстый блок ссылок. PageRank обрабатывает каждую ссылку отдельно, а более эффективный метод BlockRank рассматривает все эти внутренние ссылки сайта как одно целое и, только покончив с ними, переходит к внешним ссылкам.

• Второй метод использует экстраполяцию PageRank. Прежде чем сканировать веб, выдвигаются определенные предположения о важности сайта. В процессе сканирования эти предположения либо подтверждаются, либо отбрасываются, так что по мере увеличения числа обработанных ссылок растет и точность оценок. Когда собирается достаточное количество свидетельств, производится экстраполяция — то есть делается догадка о ранге сайта. По сравнению с PageRank, где ранг сайта определяется лишь по окончании обширного обследования веба, метод экстраполяции работает на 50% быстрее.

• Третий метод, называемый Adaptive PageRank, опирается на тот факт, что сайты с более низким рангом обычно обсчитываются быстрее, чем сайты с более высоким. Отказавшись от дальнейшей обработки таких быстро обсчитываемых сайтов, можно увеличить быстродействие на величину до 50%.

Хотя у каждого из этих методов свои преимущества, стэнфордская команда уверена, что в сочетании они обеспечат еще лучший результат. «При использовании всех этих методов возможно еще большее ускорение, — говорит один из участников проекта Сепандар Камвар. — Наши предварительные эксперименты показывают, что их комбинация сделает вычисление PageRank впятеро быстрее. Однако нам предстоит решить ряд проблем. Сейчас мы ближе к тематическому PageRank, чем к персонализированному ранжированию».

Пока теории стэнфордцев остаются теориями — не похоже, чтобы они были как-то связаны с самим Google. «Google приветствует любой вклад в дальнейшее изучение методов анализа гиперссылок в вебе», — ответил представитель компании на вопрос CNETAsia о том, рассмотрит ли Google возможность использования предложений ученых.