О сервисе WebGround

Ваша тема


Новости сайта

Литература

обложка книгиИнтернетика. Навигация в сложных сетях: модели и алгоритмы
Большакова Е.И., Клышинский Э.С., Ландэ Д.В., Носков А.А., Пескова О.В., Ягунова Е.В. Автоматическая обработка текстов на естественном языке и компьютерная лингвистикаАвтоматическая обработка текстов на естественном языке и компьютерная лингвистика (pdf)
Ягунова Е.В., Макарова О.Е., Антонова А.Ю., Соловьев А.Н. Разные методы компрессии в исследовании понимания новостного текстаРазные методы компрессии в исследовании понимания новостного текста (pdf)
Крылова И.В, Пивоварова Л.М., Савина А.В., Ягунова Е.В. Исследование новостных сегментов российской «снежной революции»: вычислительный эксперимент и интуиция лингвистовИсследование новостных сегментов российской «снежной революции»: вычислительный эксперимент и интуиция лингвистов (pdf)
Ягунова Е.В. Исследование перцептивной устойчивости фонем как элементов речевой цепиИсследование перцептивной устойчивости фонем как элементов речевой цепи (pdf)
Ягунова Е.В. Вариативность структуры нарратива и разнообразие стратегий пониманияВариативность структуры нарратива и разнообразие стратегий понимания (pdf)
Ягунова Е.В., Пивоварова Л.М. Экспериментально-вычислительные исследования художественной прозы Н.В. ГоголяЭкспериментально-вычислительные исследования художественной прозы Н.В. Гоголя (pdf)
Ягунова Е.В. Вариативность стратегий восприятия звучащего текстаВариативность стратегий восприятия звучащего текста (pdf)
Ягунова Е.В. Спонтанный нарратив у детей и у взрослыхСпонтанный нарратив у детей и у взрослых (pdf)
Ягунова Е.В. Исследование избыточности русского звучащего текстаИсследование избыточности русского звучащего текста (pdf)
Ягунова Е.В. Фонетические признаки опорных сегментов и восприятие русского текстаФонетические признаки опорных сегментов и восприятие русского текста (pdf)
Ягунова Е.В. Коммуникативная и смысловая структура текста и его восприятиеКоммуникативная и смысловая структура текста и его восприятие (pdf)
Ягунова Е.В. Где скрывается смысл бессмысленного текста?Где скрывается смысл бессмысленного текста? (pdf)
Ягунова Е.В. Эксперимент в психолингвистике: Конспекты лекций и методические рекомендацииЭксперимент в психолингвистике: Конспекты лекций и методические рекомендации (pdf)
Ягунова Е.В. Теория речевой коммуникацииТеория речевой коммуникации (pdf)
Антонова А.Ю., Клышинский Э.С., Ягунова Е.В. Определение стилевых и жанровых характеристик коллекций текстов на основе частеречной сочетаемостиОпределение стилевых и жанровых характеристик коллекций текстов на основе частеречной сочетаемости (pdf)
Ягунова Е.В. Эксперимент и вычисления в анализе ключевых слов художественного текстаЭксперимент и вычисления в анализе ключевых слов художественного текста (pdf)
Ягунова Е.В. Ключевые слова в исследовании текстов Н.В. ГоголяКлючевые слова в исследовании текстов Н.В. Гоголя (pdf)
Пивоварова Л.М., Ягунова Е.В. Информационная структура научного текста. Текст в контексте коллекцииИнформационная структура научного текста. Текст в контексте коллекции (pdf)
Савина А.Н., Ягунова Е.В. Исследование коллокаций с помощью экспериментов с информантамиИсследование коллокаций с помощью экспериментов с информантами (pdf)
Ягунова Е.В., Пивоварова Л.М. От коллокаций к конструкциямОт коллокаций к конструкциям (pdf)
Пивоварова Л.М., Ягунова Е.В. Извлечение и классификация терминологических коллокаций на материале лингвистических научных текстовИзвлечение и классификация терминологических коллокаций на материале лингвистических научных текстов (pdf)
Julia Kiseleva. Grouping Web Users based on Query LogGrouping Web Users based on Query Log (pdf)
Julia_Kiseleva_Unsupervised_Query_Segmentation_Using_Click_Data_and_Dictionaries_Information.pdfUnsupervised Query Segmentation Using Click Data and Dictionaries Information (pdf)
Четыре лекции о методе
Начала предметного анализа методов (на примере метода Ф.Бэкона)
Вариативность стратегий восприятия звучащего текста
Извлечение и классификация коллокаций на материале научных текстов. Предварительные наблюдения
Природа коллокаций в русском языке. Опыт автоматического извлечения и классификации на материале новостных текстов
Войтишек А. Повторы. Лирические рефреныПовторы. Лирические рефрены (pdf)
Войтишек А. Новое. Лирические рефреныНовое. Лирические рефрены (pdf)
Войтишек А. Всё об одном и том жеВсё об одном и том же. 500 лирических рефренов к 50-летию (pdf)
Войтишек А. Тысяча-часть-1Тысяча-часть-1 (pdf)
Войтишек А. Тысяча-часть-2Тысяча-часть-2 (pdf)
Войтишек А. АлфавитАлфавит (pdf)



2.4. Алгоритмы поиска в пиринговых сетях

 

Главная задача информационного поиска в децентрализованных пиринговых сетях (сетях P2P) – быстрое и эффективное нахождение наиболее релевантных откликов на запрос, передаваемый от узла ко всей сети. В частности, как всегда актуальна задача получения качественного результата при общем уменьшении сетевого трафика [104].

 

2.4.1. Алгоритм поиска ресурсов по ключам

 

В большинстве пиринговых сетей, ориентированных на обмен файлами, используется два вида сущностей, которым приписываются соответствующие идентификаторы (ID): узлы и ресурсы (например, файлы), характеризующиеся ключами (Key), т.е. сеть может быть представлена двумерной матрицей размерности  где количество узлов, количество ресурсов. В данном случае задача поиска сводится к нахождению ID узла, на котором хранится ключ ресурса. На рис. 4. представлен процесс поиска ресурса, запускаемый с узла с ID 0 [155, 156].  В данном случае с узла с ID 0 запускается поиск ресурса с ключом 14. Запрос проходит определенный маршрут и достигает узла, на котором находится ключ 14. Далее узел с ID 14 пересылает узлу с  ID 0 адреса всех узлов, обладающих ресурсом, соответствующим ключу 14.

 

ris4-1

Рис. 4. Модель поиска ресурса по ключу

        

Рассмотрим алгоритмы поиска в пиринговых сетях, ограничившись основными методами поиска по термам.

        

2.4.2. Метод широкого первичного поиска

 

Метод широкого первичного поиска (Breadth First Search, BFS) [104] широко используется в  реальных файлообменных сетях P2P, таких как, например,  Gnutella (www.gnutella.com). Метод BFS (рис. 5) в сети P2P размерности  реализуется следующим образом. Узел  генерирует запрос, который адресуется ко всем  соседям (ближайшим по некоторым критериям узлам). Когда узел  получает запрос, выполняется поиск в его локальном индексе. Если некоторый узел  принимает запрос (Query) и обрабатывает его, то он генерирует  сообщение-отклик (QueryHit), чтобы возвратить результат. Сообщение QueryHit включает информацию о релевантных документах, которая доставляется  по сети запрашивающему узлу (рис. 5).

Когда узел  получает QueryHits от более чем одного узла, он может загрузить файл с наиболее доступного ресурса. Сообщения QueryHit возвращаются тем же путем, что и первичный запрос.

ris5-1

Рис. 5. Метод BFS

 

В BFS каждый запрос вызывает чрезмерную  нагрузку сети, так как он  передается по всем связям (в том числе и  узлам с высоким временами ожидания). Поэтому узел  с низкой пропускной способностью может стать узким местом. Одним из методов, позволяющий избежать перегрузки всей сети сообщениями заключается в приписывании каждому запросу параметра времени жизни (Time-to-live, TTL). Параметр TTL определяет максимальное число переходов, по которым можно пересылать запрос (очень важно, что именно число переходов, а не физическое время, измеряемое, например, в секундах). При типичном поиске начальное значение для TTL составляет  5-7 и уменьшается каждый раз, когда запрос пересылается. Когда TTL становится равным 0, сообщение больше не передается. BFS гарантирует высокий уровень качества поиска за счет большого числа переданых сообщений.

 

2.4.3. Метод случайного широкого первичного поиска

 

Метод случайного широкого первичного поиска (Random Breadth First Search, RBFS) был предложен  как  улучшение «наивного» подхода BFS [104]. В методе RBFS (рис. 6) узел  пересылает поисковое предписание только части узлов сети, выбранной в случайном порядке. Какая именно часть узлов – это параметр  метода RBFS.

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

ris6-1

Рис. 6. Метод RBFS

 

2.4.4. Интеллектуальный поисковый механизм

 

Интеллектуальный поисковый механизм (Intelligent Search Mechanism, ISM) является относительно новым методом поиска в сетях P2P (рис. 7). Улучшение скорости и эффективности  поиска информации с помощью данного метода достигается за счет минимизации затрат на связи, то есть на число сообщений, передающихся между узлами, и минимизации количества узлов, которые опрашиваются для каждого поискового запроса. Чтобы достичь этого,  для каждого запроса оцениваются лишь те узлы, которые наиболее соответствуют данному  запросу.

ris7-1

Рис. 7. Метод ISM

 

Интеллектуальный поисковый механизм состоит из двух компонент – профайла (profile) и способа его ранжирования, так называемого ранга релевантности. Каждый узел сети строит информационный профайл для каждого из соседних узлов. Профайл содержит последние ответы каждого из  узлов. С помощью ранга релевантности осуществляется ранжирование профайлов узлов для выбора тех соседних, которые будут давать наиболее релевантные документы по запросу. Механизм профайлов используется для того, чтобы сохранять  последние запросы, а также  количественные характеристике результатов поиска.

При реализации модели ISM используется единый стек запросов, в котором сохраняется по  запросов для  узлов. Как только стек заполняется, происходит замена «того запроса, который не использовался дольше всего» (Least Recently Used, LRU)  для сохранения последних запросов. Функция «ранг релевантности» (Relevance Rank, RR) используется узлом , чтобы  выполнять оперативную  классификацию его соседей для определения тех, которые следует опрашивать первыми по  запросу . Для вычисления ранга релевантности  каждого узла    сравнивает  со всеми запросами в структуре профайла, для которого известен список ответов на предыдущие запросы, и вычисляет :

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

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

Однако для  все запросы весят одинаково, и  дает более высокую релевантность. При  учитывается только количество результатов, возвращенных каждым узлом.

Метод ISM эффективно работает  в сетях, где узлы содержат некоторые специализированные сведения. В частности, исследование сети Gnutella показывает, что качество поиска очень зависит от «окружения» узла, с которого задается запрос. Большая проблема в методе ISM состоит в том, что поисковые сообщения могут циклично проходить одни и те же узлы сети, не достигая некоторых ее частей. Чтобы разрешить эту проблему для охвата большей части сети в [156] был описан подход, при котором для  каждого запроса выбиралось небольшое подмножество случайных узлов, добавляляющееся к набору релевантных узлов.

Существуют и другие подходы решения этой проблемы, например, применяемый в протоколе BGP4 (RFC 1771), где каждый запрос сохраняет «историю» - список узлов, через которые он уже прошел.

 

2.4.5. Методы «большинства результатов по прошлой эвристике»

 

В [151, 152] был представлен метод «большинства результатов по прошлой эвристике» «>RES» (рис. 8), в котором каждый узел  пересылал запрос подмножеству своих узлов, образованному на основании некоторой обобщенной статистики.

Запрос в методе >RES является удовлетворительным, если выдается  или больше результатов ( – некоторая постоянная). В методе >RES узел  пересылает запросы к  узлам, выдавшим наибольшие результаты для последних  запросов.   В экспериментах  изменялось от 1 до 10 и таким путем метод >RES варьировался  от  BFS до метода, называемого глубинным первичным поиском (Depth-first-search).  

ris8-1

Рис. 8. Метод >RES

 

Метод >RES подобен методу ISM,  но использует более простую информацию об узлах. Его главный недостаток по сравнению с ISM – отсутствие анализа параметров узлов,  содержание которых связано с запросом. Поэтому метод >RES характеризуется скорее как количественный, а не качественный подход. Из опыта известно, что >RES  хорош тем, что он маршрутизирует запросы в большие сегменты сети (которые возможно, также содержат более релевантные ответы). Он  также захватывает соседей, которые менее перегружены, начиная с тех, которые обычно возвращают больше результатов.

 

2.4.6. Метод «случайных блужданий»

 

В [109] представлен  алгоритм «случайных блужданий» (Random Walkers, Algorithm, RWA). Ключевая идея метода заключается в том, что каждый узел случайным образом пересылает сообщение с запросом, именуемое «посылкой» одному из соседних узлов. Чтобы сократить время, необходимое для получения результатов, вместо одной «посылки» рассматривается   независимых посылок, последовательно запущенных с поискового узла. Ожидается, что «-посылок» после  шагов достигнет тех же результатов, что и одна посылка за  шагов.  Этот алгоритм напоминает  метод RBFS, но в  RBFS  каждый узел пересылает сообщение запроса части соседей. К тому же, в RBFS предполагается экспоненциальное увеличение пересылаемых сообщений, а в методе случайных блужданий – линейное.  Оба метода - и RBFS, и RWA не используют никаких явных правил для  того чтобы адресовать поисковый запрос к наиболее релевантному содержанию.

         Еще одной методикой, подобной RWA,  является «адаптивный вероятностный поиск» (Adaptive Probabilistic Search, APS) [156]. В  APS каждый узел развертывает на своих ресурсах локальный индекс, содержащий значения условных вероятностей для каждого соседа, который  может быть выбран для обработки следующего запроса. Главное отличие от RWA в данном случае -  это то, что в APS узел использует в качестве обратной связи результаты предыдущих поисков (в виде условных вероятностей) вместо полностью случайных переходов. Поэтому метод APS часто дает лучшие результаты, чем RWA.