Тезисы докладов

В настоящее время большой популярностью обладает группа алгоритмов информационного поиска, использующая сеть Веб в виде направленного графа. При этом вершинами графа являются Веб-страницы, а ребрами - ссылки между этими страницами. Данный граф принято называть графом Веб [1].

Алгоритмы, использующие граф Веб можно разбить на несколько групп, среди которых выделяются следующие: алгоритмы ранжирования результатов поисковых запросов; анализ графа Веб с целью выделения так называемых интернет-сообществ (группы ресурсов, связанных по какому-либо признаку); анализ графа Веб с целью оптимизации его структуры и многие другие.

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

Одним из вариантов решения данной проблемы является распределенная модель графа Веб. При этом каждый из ее сегментов обладает средствами по обработке, поддержанию целостности и актуальности, динамическому расширению своего содержания [2].

Формирование сегментов распределенной модели производится на основе выделения интернет-сообществ. При этом каждый сегмент содержит одну или более силносвязных компонент графа.
Данный подход к формированию сегментов обладает следующими преимуществами:

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

2. Динамическая балансировка загрузки сегментов. Статистика, собираемая при прохождении запросов на поиск/модификацию используется для динамического конфигурирования состава сегментов.

3. Возможность проведения анализа процессов, происходящих в графе Веб.

В докладе рассматриваются вопросы программной реализации представленной системы.

Литература

1. И. Некрестьянов, Н. Пантелеева. Системы текстового поиска для Веб. Программирование, 28(4): 207-225, 2002.

2. А. Третьякевич. Использование графа Веб для решения задач информационного поиска. Материалы конференции ИКИ-2003, 2003.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск