Обработка исходных данных коллекции ClueWeb12

Размещено на http://www.allbest.ru/

Содержание

Введение

1. Описание исходных данных

2. Технологии

3. Описание формата WARC

3.1 Файл и модель запись

4. Работа с исходными данными

4.1 Предварительная подготовка коллекции документов

4.2 Извлечение содержимого веб-страниц

4.3 Преобразование содержимого страниц с помощью TF-IDF

4.4 Работа с веб-графом

4.5 Обработка дополнительных данных

5. Имплементация поиска

Выводы

Литература



Введение

информация поиск интернет

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

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

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

Необходимо смоделировать ситуацию, в которой web-crawler сможет найти страницу, которая будет максимально релевантная заданному запросу, переходя от одного сайта к другому, на основании ссылок, содержащихся на каждой странице.

Необходимо написать программу, которая будет разбирать архив формата WARC, извлекать из него страницы и строить Term Frequency Vector. Каждой страницы i из коллекции будет соответствовать Term Frequency Vector t_i. Далее формируется запрос, состоящий из нескольких ключевых слов. Начиная с сайта, выбранного случайным образом, и переходя по ссылкам- “соседям”, мы пытаемся найти такую страницу r, расстояние Dist(t_r, t_q) до которой по косинусной мере будет максимально приближено к 1.

Базовое представление алгоритма поиска:

1. Задаем страницу, которую требуется найти

2. Задаем запрос q

3. Рассматриваем страницу p, выбранную случайным образом в качестве начальной страницы

4. Считаем расстояние Dist(t_p, t_q) к странице p и всех ее соседей N(p)

5. Если в окрестности N(p) нет страницы до которой расстояние было бы больше чем Dist(t_p, t_q), алгоритм останавливается и считается, что страница p - искомая.

6. Переходим в ту страницу p' из N(p) расстояние до которой меньше всего и переходим к шагу 1.

В результате описанного должна получиться статистика, насколько часто такой способ поиска приводит к желаемому результату.



1. Описание исходных данных

В качестве исходных данных был использован датасет The ClueWeb12. Данный датасет представляет из себя слепок интернета за 2012 год, Он состоит из 733 019 372 страниц на английском языке, собранных в период с 10 февраля 2012 года по 10 мая 2012 года. Размер датасета: 6 Терабайт в архивированном виде, 27 Терабайт в распакованном виде. Ранее лаборатория Carnegie Melon University создавала датасет ClueWeb09. (добавить описание)

Датасет представляет из себя собранные веб-документы в формате WARC, собранные следующим способом: большая часть документов была собрана с помощью программы Internet Archive's Heritrix Web Crawler, распределенной между пятью серверами со стандартными настройками.

Изначально датасет состоял из 2 820 500 уникальных ссылок. Данный список был сгенерирован из 10 000 000 ссылок из датасета ClueWeb09, которые имели наилучший результат PageRank. Далее полученные данные были отсортированы с помощью Waterloo spam scores, для отсеивания спам-ссылок. Далее были проанализированы самые популярные сайты англоговорящих стран, их 262. Количество сайтов, добавленных из каждой страны соответствовало населению каждой страны, для примера: США ( 71%), Великобритания (14 %), Канада (7.7%), Австралия (5.2%), Ирландия (3.8 %), Новая Зеландия (3.7%). Также были предоставлены 5 950 ссылок на сайты, связанные с туризмом и путешествиями.

Также были отсортированы сайты, распространяющие спам, вирусы и прочие ссылки, которые не могут быть востребованы для исследовании и анализа структуры Web. Черный список был взят с URLBlacklist.com. Web-crawler фильтровал ссылки, содержащие спам, фишинг, вирусы, ресурсы для хранения файлов (файловые хостинги).

Также были собраны твиты из Twitter Gardenhose Stream. Это было сделано с целью сделать Web Graph более связным.

Web-crawler был настроен на захват текста, css, xml и файлы javascript, изображения и заголовки HTTP типа Response. Программа пропускала файлы мультимедиа: аудио и видео, а также всевозможные архивы: (zip, tar, gz, sit, hqx).

Несмотря на то, что изображения были собраны, из-за соображений размера датасета (более 27 Терабайт в распакованном виде) они недоступны.

После предварительной фильтрации страниц, собранная коллекция была преобразована следующим образом:

1. Было удалено все, что связано с robots.txt

2. Были удалены записи типа WARC Request

3. Были удалены все записи с кодом ответа, отличным от 2хх и 3хх

4. Были удалены все страницы на других языках с помощью Cybozu Labs - библиотека для определения языка на Java.

5. Были удалены все ссылки и страницы, содержащие контент для взрослых

6. Были удалены все документы, размер которых составлял более 10 Мегабайт

7. Были удалены документы, содержащие более миллиона терминов

8. Разделение всего датасета на сегменты, каждый из которых содержит приблизительно 50 миллионов документов. Каждый сегмент разделен на архив формата WARC, размер каждого такого архива составляет приблизительно 1 Гигабайт при распаковке. Данные архивы организованы по директориям, каждая из которых содержит приблизительно по 100 таких архивов.



2. Технологии

Для обработки данного датасета был выбран язык Java. Для обработки архивов формата WARC изначально была выбрана библиотека JWAT

(Java Web Archive Web Toolkit). Однако данная библиотека имеет странную ошибку при чтении заархивированных WARC файлов. Из -за невозможности разархивировать всю коллекцию (как было описано раннее, размер составляет более 27 Терабайт) было отдано предпочтение реализации webarchive-commons с небольшими дополнениями, так как архивы WARC в данном датасете содержат дополнительные нестандартные поля).

Python в качестве языка программирования был отвергнут, из-за недостаточной скорости обработки архивов и текста.

В качестве обработки текста в формат Term Frequency- Inverted Document Frequency была выбрана библиотека Apache Lucene. Для обработки извлеченных из архива страниц была выбрана библиотека JSoup. Датасет сопровождается дополнительными данными:

Таблица соответствия номера ноды в Веб-графе с URL, таблица соответствия URL с уникальным идентификатором внутри датасета, Веб-граф в расширенной версии (с содержанием нод, которые не входят в датасет). Для хранения вышеперечисленной дополнительной информации была использована база данных MYSQL. Для обработки графа была использована библиотека WebGraph. Данная библиотека была специально разработана для изучения Веб-графов.



3. Описание формата WARC

WARC (Web ARChive) - формат, который предлагает “связывание” множество записей ресурсов (в нашем случае ресурсы- это веб-страницы), каждый из которых представляет набор простых текстовых заголовков и обязательных блоков данных в одном файле. Формат типа WARC является расширением формата ARC, который традиционно использовался программами типа web-crawler для хранения результатов как последовательность блоков содержимого, извлеченного из Всемирной Сети Интернет. Каждый файл имел заголовок в одну строку, который очень поверхностно описал содержимое данного файла и его длину. Далее следовали “сообщения-ответы” и непосредственно содержимое данных ответов. Оригинальный формат ARC использовался организацией Internet Archive с 1996 года для управления миллиардами документов.

Основанием для расширения формата ARC послужили множественные дискуссии и опыт организации International Internet Preservation Consortium (IIPC), куда входят национальные библиотеки Австралии, Канады, Дании, Финляндии, Франции, Исландии, Италии, Норвегии, Швеции, Великобритании и США.

Стандарт WARC предлагается как стандартный способ структуризации, управления и хранения миллиардов веб-ресурсов, собранных из Всемирной Сети Интернет и не только. Он должен быть использован как основа для построения приложений сохранения, доступа и обработки контента, собранных программами типа web-crawler.

Создание, хранение и воспроизведение сохраненного содержимого зависит от конкретной имплементации.

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

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

3.1 Файл и модель записи

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

Материал (метаданные, преобразованное содержимое) который обеспечивает дополнительную информацию о заархивированном содержимом.

Запись WARC состоит из заголовка и блока содержимого записи. Между записями WARC принято оставлять две пустые строки.

Основные и обязательные записи, которые должна содержать каждая WARC запись:

1) WARC-Record-ID = "WARC-Record-ID" ":" uri

URI (Uniform Resource Identifier) - строка, определяющая уникальное имя ресурса, содержимое которого хранится в данной записи.

2) Content-Length = "Content-Length" ":" 1*DIGIT

Непосредственно, длина содержимого, хранящегося в данной записи.

3) WARC-Date = "WARC-Date" ":" w3c-iso8601

w3c-iso8601 = <YYYY-MM-DDThh:mm:ssZ>

Формат времени по стандарту [ISO8601]- 14 цифр.

4) WARC-Type = "WARC-Type" ":" record-type

record-type = "warcinfo" | "response" | "resource"

| "request" | "metadata" | "revisit"

| "conversion" | "continuation" | future-type

future-type = token

Тип WARC- записи. Каждый WARC файл должен содержать

warcinfo, для понимания содержимого архива.

5) Сontent-Type = "Content-Type" ":" media-type

media-type = type "/" subtype *( ";" parameter )

type = token

subtype = token

parameter = attribute "=" value

attribute = token

value = token | quoted-string

Согласно [RFC2045] данное поле заголовка описывает информацию, содержащуюся в блоке записей. В качестве примера, записи запроса (request) и ответа (response) протокола HTTP будут выглядеть следующим образом:

'application/http; msgtype=request' и 'application/http; msgtype=response'

6) WARC-Concurrent-To = "WARC-Concurrent-To" ":" uri

Это поле предназначено в основном для того, чтобы объединить все события захвата данного ресурса.

7) WARC-IP-Address = "WARC-IP-Address" ":" (ipv4 | ipv6)

ipv4 = <"dotted quad">

ipv6 = <per section 2.2 of RFC1884>

Интернет адрес по протоколу IP, с которым была организовано соединение для извлечение содержимого, хранящегося в записи

Остальные поля заголовка WARC являются необязательными, и могут быть добавлены в зависимости от конкретной имплементации программы, которая организует сбор данных с просторов сети Интернет.



4. Работа с исходными данными

4.1 Предварительная подготовка коллекции документов

Несмотря на внушительный размер датасета - 2 жестких диска по 3 Терабайта каждый, 27 Терабайт в распакованном виде, проект ClueWeb12 не является самым крупном архивом на данный момент - наиболее известным представителем на данный момент является проект Common Crawl. Размер их датасета уже переходит на Петабайты информации, в их коллекции более 5 000 000 000 сохраненных веб-ресурсов на разных языках, в то время как ClueWeb12 преследовал более скромные цели - около 733 000 000 сайтов, исключительно на английском.

Однако несмотря на все, казалось бы, преимущества датасета Common Crawl, он представляет из себя всего лишь сгруппированные архивы данных, без каких-либо сопутствующих данных. Например, построение Веб-графа ложится на плечи исследователей, к тому же, несмотря на возможность выкачать весь датасет, который обновляется раз в несколько месяцев (последний раз - в феврале 2016 года), трудно представить, сколько ресурсов понадобится лишь для хранения такого огромного объема информации. И это уже не говоря о том, что для исследования потребуется внушительные ресурсы, целые “фермы” мощных серверов.

Ранее Lemur Project предпринимал амбициозную попытку создать слепок интернета на нескольких языках, это был датасет ClueWeb09. Однако из-за настройки программ коллекционирования информации датасет содержал много повторении, пропусков и множество других проблем. Проект учел свои предыдущие ошибки, и на базе ClueWeb09 сделал ClueWeb12.

В нагрузку к самому архиву, проект представляет дополнительные материалы, такие как Веб-граф (более 6 000 000 вершин, для более полного представления структуры Интернета), и информация для перехода между вершинами и непосредственно URL ресурсов. Такие подготовленные данные сильно помогают в анализе навигационных свойств.

Были предприняты попытки обработать всю коллекцию целиком, однако от этой затеи пришлось отказаться. Обработка одного сегмента (20 директорий с 100 файлами формата WARC в каждой) занимала более 20 часов на доступной конфигурации. Были предприняты попытки использовать Apache Hadoop, однако имея в распоряжении только две физические ноды (компьютер и ноутбук), это не давало нужного прироста производительности.

Специально для таких ситуаций, Lemur Project предусмотрел отдельный датасет, собранный из ClueWeb12 - ClueWeb12 B13. Данный датасет представляет из себя 7% выборку из всей созданной коллекции. Это было сделано следующим образом: из каждого файла WARC был взят каждый 14 документ WARC формата WARC-response. В архиве весь датасет весит около 387 Гигабайт, 1.5 Терабайта в распакованном виде. Данный объем уже казался вполне выполнимой задачей на доступных ресурсах. В качестве основы для построения алгоритма поиска была взята данная производная коллекция.

Далее, необходимо было изучить сам формат, в котором хранится вся коллекция- WARC. После просмотра спецификаций, было принято решение использовать библиотеку JWAT - Java Web ARChive. Данная библиотека написана на языке Java, как и большинство программ для сбора, обработки и воспроизведения содержимого веб-страниц.

В первую очередь библиотека привлекала встроенной возможностью обрабатывать файлы формата WARC без необходимости разархивации из формата gunzip (.gz).

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

Также не были учтены специфические поля заголовка, которые были добавлены в каждый файл WARC:

1) WARC-Number-of-Documents - количество документов в данном файле WARC

2) WARC-File-Length - длина данного архива в распакованном виде

3) WARC-Data-Type - специальные обозначения для типов документов, которые были собраны в данном архиве. (wb: Web crawl, tw: Twitter links crawl, wt: WikiTravel crawl)

Также запись WARC типа response имела свое специфичное поле

WARC-TREC-ID. Это уникальный идентификатор, который определяет позицию конкретного документа во всей коллекции ClueWeb12. Однако после изначального сбора и обработки собранных данных, были совершены ошибки, что привело к появлению дубликатов ресурсов. Данный идентификатор был присвоен до фильтрации коллекции с целью удаления дубликатов.

В итоге было принято решение взять за основу реализацию WebArchive-Commons и добавить необходимые специфичные поля заголовка.

Также пришлось взять стандартную реализацию чтения потока из архива GZip из стандартных библиотек языка Java.

4.2 Извлечение содержимого веб страниц

После первичной обработки и извлечения содержимого записи, мы получаем содержимое страницы. Данной обработки недостаточно, чтобы начинать преобразование Tf-Idf (Term Frequency- Inverted Document Frequency), что необходимо для применения алгоритма поиска.

На извлеченной странице содержится огромное количество материала, помимо непосредственного текста - файлы css, элементы javascript, ссылки на ресурсы CDN (Content Delivery Network) для отрисовки стилей страницы или анимации и картинок.

Для данной обработки была выбрана библиотека Jsoup. Она обладает всеми необходимыми методами для извлечения любого элемента страницы.

4.3 Преобразование веб-страниц с помощью TF-IDF

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

TF-IDF (Term Frequency- Inverted Document Frequency) - мера статистики, которая используется для оценки важности слова в контексте документа, который является в свою очередь, частью корпуса. Корпус- коллекция документов.

Мера TF-IDF используется в анализе текстов и информационном поиске в качестве одного из критериев релевантности документа поисковому запросу, при расчете меры близости документов при кластеризации.

TF (term frequency - частота слова) - отношение числа вхождения некоторого слова к общему количеству слов документа. Таким образом, оценивается важность слова в пределах отдельного документа.

,

где есть число вхождений слова в документ, а в знаменателе - общее число слов в данном документе.

IDF (inverse document frequency - обратная частота документа) - инверсия частоты, с которой некоторое слово встречается в документах коллекции. Учёт IDF уменьшает вес широкоупотребительных слов. Для каждого уникального слова в пределах конкретной коллекции документов существует только одно значение IDF.

,

|D| - количество документов в корпусе;

 - количество документов, в которых встречается (когда ).

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

Таким образом, мера TF-IDF является произведением двух сомножителей:

Большой вес в TF-IDF получат слова с высокой частотой в пределах конкретного документа и с низкой частотой употреблений в других документах.

Для преобразования страниц с помощью TF-IDF была выбрана библиотека Apache Lucene на языке Java. Это высокопроизводительная библиотека специально предназначена для имплементации приложений текстового поиска.

4.4 Работа с Веб-графом

В качестве одного из приложений к основной коллекции ClueWeb12 Lemur Project предоставляет Веб-граф. Вершины в данном графе организованы следующим образом:

1) Вершина 0 - пустая, это сделано для поддержки формата BVGraph

2) Первые 733 019 372 (не считая 0) вершины - вершины, которые представляют собой документы из коллекции

3) Следующие 245 388 725 вершин соответствуют вершинам, которые изначально входили в коллекцию, однако были удалены.

4) Остальные 5 279 298 498 вершин- не входят в собранную коллекцию

Граф предоставлен в двух форматах - стандартном формате ASCII и в специальном BVGraph. С последним форматом работает библиотека WebGraph. Данный формат предпочтительнее, так как BVGraph весит значительно меньше - всего 56 Гигабайт с файлом смещений (offsets) 3.6 Гигабайт. В стандартном формате ASCII граф весит рекордные 617 Гигабайт в распакованном виде. Главное преимущество (помимо размера), которое может предоставить граф в формате BVGraph - случайный (random) доступ к вершинам и их соседям. В то время как чтение ASCII файла может занять огромное количество времени, так как доступ к нему можно обеспечить лишь последовательно (sequential).

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

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

Библиотека WebGraph предоставляет метод преобразования графа из формата ASCII во внутренний формат BVGraph, однако предварительно необходимо было избавиться от ненужных вершин. Граф в формате ASCII представляет из себя следующее - на первой строке файла пишется общее количество вершин, далее, на каждой строке идет перечисление всех соседей данной вершины (строка представляет собой порядковый номер вершины), между этими строками специально ставится пустая строка. Из-за огромного размера файла (более 617 Гигабайт) данная попытка тоже не увенчалась успехом. В любом случае, при трансформации графа в формат BVGraph происходит переименование вершин, соответственно для вновь построенного графа для датасета ClueWeb12 B13 придется содержать структуру, которая будет приводить номер вершины нового графа к вершине “старого”. Данную структуру придется хранить в базе данных.. В ходе работы поиска уже приходится обращаться к двум таблицам данных, одна преобразует номер вершины в URL, а другая таблица превращает WARC-TREC-ID (уникальный идентификатор, как было описано ранее) в URL. И это значительно увеличит время выполнение поиска.

4.5 Обработка дополнительных данных

Помимо Веб-графа, Lemur Project предоставляет два файла - Clueweb12_url2nodeId (Преобразование номера вершины Веб-Графа в URL) и Clueweb12_b13_docid2url (Соответствие WARC-TREC-ID и URL). Данные файлы помогают в полной мере работать с Веб-графом и коллекцией, на основании которой этот граф был создан. Проблема начинается с того, что эти данные представлены в простых текстовых файлах и их размер впечатляет- 617 Гигабайт и 47.3 Гигабайт соответственно.

Принимая во внимание тот факт, что для производной коллекции ClueWeb12_B13 не требуется все данные, которые содержатся в этих файлах. Поэтому, принимая во внимание что данная коллекция значительно меньше (7% от общей выборки) оба файлы были обработаны тем же способом, что и коллекция архивов. Из файлов были извлечены каждая 14 запись, это помогло значительно сократить размер конечных файлов - 41 Гигабайт и 5.7 Гигабайт соответственно.

Далее принималось решение, каким образом лучше организовать доступ к данным в этих файлах. Было принято решение организовать базу данных MySQL. Выбор пал на данную СУБД, как одну из самых распространенных и популярных. Были организованы две таблицы: NodeID_to_URL и DocID_to_URL для каждого из файлов соответственно.



5. Имплементация поиска

Имплементация алгоритма делится на две отдельные программы: первая программа обрабатывает веб-страницы, которые извлекаются из коллекции и приводит их к Term Vectors; Вторая часть программы непосредственно производит поиск по полученным векторам.

Блок-схема первой части программы для каждого архива WARC:

Стоит отметить, что преобразование TF-IDF для получения так называемых Term Vectors происходит единожды. Также для проверки результатов поиска был построен индекс в формате Apache Lucene. Первую программу следует воспринимать как подготовку к имплементации алгоритма поиска.

Во второй программе происходит непосредственный поиск. Он организуется следующим образом:

1. Создается текстовый запрос

2. Берется конечная вершина со значением, близким к 1 по косинусной мере

3. Берется случайно выбранная вершина как старт

4. Из Веб-графа извлекается соседи стартовой вершины

3.1 Соседи проверяется на вхождение в коллекцию ClueWeb12. Происходит отсеивание вершин, выходящих за границы.

3.2 Оставшиеся соседи проверяются на вхождение в коллекцию ClueWeb12_B13. Происходит отсеивание вершин, выходящих за границы.

4. Поиск соответствия номера каждой из вершин в таблице DocId_to_URL, получаем WARC-TREC-ID

5. Получаем идентификаторы положения документов в индексе Apache Lucene

6. Считаем расстояние по косинусной мере всех соседей и стартовой вершины.

7. Если искомая вершина не достигнута, переходим к шагу 3. В качестве стартовой вершины выбирается вершина с наилучшим результатом по косинусной мере.



Блок-схема:

В качестве поисковых запросов были взяты темы TREC с 201 по 300. TREC- Text Retrieval Conference- ежегодное событие, на котором происходит тестирование различных технологий по извлечению информации. В 2014 году проводилось расширенное тестирование способов поиска информации в датасете ClueWeb12, а в частности производного датасета ClueWeb12_B13. Отсюда и настолько специфичный набор тем.

Ниже представлена таблица тем TREC:

TREC topic number	Topic
201	raspberry pi
202	uss carl vinson
203	reviews of les miserables
204	rules of golf
205	average charitable donation
206	wind power
207	bph treatment
208	doctor zhivago
209	land surveyor
210	golf gps
211	what is madagascar known for
212	home theater systems
213	carpal tunnel syndrome
214	capital gains tax rate
215	maryland department of natural resources
216	nicolas cage movies
217	kids earth day activities
218	solar water fountains
219	what was the name of elvis presley's home
220	nba records
221	electoral college 2008 results
222	male menopause
223	usda food pyramid
224	making chicken soup from scratch
225	black and gold
226	traverse city
227	i will survive lyrics
228	hawaiian volcano observatories
229	beef stroganoff recipe
230	world's biggest dog
231	what are the seven deadly sins
232	hurricane Irene flooding in manville, nj
233	hair dye
234	dark chocolate health benefits
235	ham radio
236	symptoms of mad cow disease in humans
237	lump in throat
238	george bush sr bio
239	frank lloyd wright biography
240	presidential middle names
241	what is a wiki
242	cannellini beans
243	afghanistan flag
244	old town Scottsdale
245	roosevelt island
246	civil war battles in south Carolina
247	rain man
248	eggs shelf life
249	occupational therapist
250	ford edge problems
251	identifying spider bites
252	history of orcas island
253	tooth abscess
254	barrett's esophagus
255	teddy bears
256	patron saint of mental illness
257	holes by louis sachar
258	hip roof
259	carpenter bee
260	the american revolutionary
261	folk remedies sore throat
262	balding cure
263	evidence for evolution
264	tribe formerly living in alabama
265	F5 tornado
266	symptoms of heart attack
267	feliz navidad lyrics
268	benefits of running
269	marshall county schools
270	sun tzu
271	halloween activites for middle school
272	dreams interpretation
273	wilson's disease
274	golf instruction
275	uss cole
276	how has african american music influence history
277	bewitched cast
278	mister rogers
279	game theory
280	view my internet history
281	ketogenic diet
282	nasa interplanetary missions
283	hairdyes in pa
284	where to find morel mushrooms
285	magnesium rich foods
286	common schizophrenia drugs
287	carotid cavernous fistula treatment
288	fidel castro
289	benefits of yoga
290	norway spruce
291	sangre de cristo mountains
292	history of electronic medical record
293	educational advantage of social networking sites
294	flowering plants
295	how to tie a windsor knot
296	recycling lead acid batteries
297	altitude sickness
298	medical care and jenovah's witnesses
299	pink slime in ground beef
300	how to find the mean

Результаты

После имплементации поиска было произведено следующее тестирование: для каждого запроса было произведено по 10 запусков программы. Ниже, в таблицах приведены результаты тестирования по каждому запросу:

Поля таблиц:

1) target_trec_id- уникальный идентификатор ресурса в коллекции ClueWeb12_B13- желаемый результат поиска

2) experiments - Поле тестирования программы, где 0 - поиск завершился неудачей, а 1 - поиска завершился успехом

3) path_length - длина пути, в случае успеха



Таблица 1: Запрос “raspberry pi”

target_trec_id	clueweb12-1700tw-22-12689
experiments	0	1	1	0	1	0	1	0	0	0
path_length	n/a	3	7	n/a	4	n/a	2	n/a	n/a	n/a

Таблица 2: Запрос “uss carl vinson”

target_trec_id	clueweb12-0602wb-40-19723
experiments	1	0	0	0	0	0	1	0	1	0
path_length	3	n/a	n/a	n/a	n/a	n/a	5	n/a	4	n/a

Таблица 3: Запрос “ reviews of les miserables ”

target_trec_id	clueweb12-0010wb-28-31568
experiments	0	0	0	0	1	1	1	0	1	1
path_length	n/a	n/a	n/a	n/a	2	1	9	n/a	4	3

Таблица 4: Запрос ”rules of golf”

target_trec_id	clueweb12-1512wb-87-09536
experiments	1	1	1	0	1	0	0	0	0	1
path_length	2	5	7	n/a	3	n/a	n/a	n/a	n/a	8

Таблица 5: Запрос ”average charitable donation”

target_trec_id	clueweb12-0210wb-94-21302
experiments	0	0	0	0	0	1	1	0	1	0
path_length	n/a	n/a	n/a	n/a	n/a	1	4	n/a	6	n/a

Таблица 6: Запрос ” wind power”

target_trec_id	clueweb12-1515wb-62-21488
experiments	0	0	0	0	1	0	0	0	0	1
path_length	n/a	n/a	n/a	n/a	1	n/a	n/a	n/a	n/a	9

Таблица 7: Запрос ” bph treatment”

target_trec_id	clueweb12-1905wb-46-06917
experiments	1	1	1	1	1	0	1	1	0	1
path_length	3	1	2	5	4	n/a	9	8	n/a	3

Таблица 8: Запрос ” doctor zhivago”

target_trec_id	clueweb12-0700tw-75-14955
experiments	0	0	0	1	0	1	1	1	0	1
path_length	n/a	n/a	n/a	7	n/a	2	5	1	n/a	1

Таблица 9: Запрос ” land surveyor”

target_trec_id	clueweb12-0211wb-61-09967
experiments	0	0	0	1	1	1	0	1	0	0
path_length	n/a	n/a	n/a	3	7	4	n/a	8	n/a	n/a

Таблица 10: Запрос “golf gps”

target_trec_id	clueweb12-1508wb-62-14300
experiments	1	1	0	1	0	1	0	0	0	0
path_length	1	6	n/a	2	n/a	7	n/a	n/a	n/a	n/a

Таблица 11: Запрос “what is madagascar known for”

target_trec_id	clueweb12-0807wb-32-04301
experiments	0	1	0	0	1	1	1	0	1	0
path_length	n/a	3	n/a	n/a	4	5	7	n/a	8	n/a

Таблица 12: Запрос “home theater systems”

target_trec_id	clueweb12-1103wb-96-17731
experiments	1	1	1	0	0	0	1	0	0	0
path_length	5	3	2	n/a	n/a	n/a	11	n/a	n/a	n/a

Таблица 13: Запрос “carpal tunnel syndrome”

target_trec_id	clueweb12-0812wb-60-28452
experiments	0	0	1	1	1	1	1	0	0	0
path_length	n/a	n/a	4	7	3	2	1	n/a	n/a	n/a

Таблица 14: Запрос “capital gains tax rate”

target_trec_id	clueweb12-0011wb-62-03765
experiments	1	1	1	0	0	0	1	0	1	0
path_length	8	2	2	n/a	n/a	n/a	7	n/a	5	n/a

Таблица 15: Запрос “maryland department of natural resources”

target_trec_id	clueweb12-0004wb-72-22379
experiments	0	1	0	0	1	0	0	0	1	1
path_length	n/a	5	n/a	n/a	1	n/a	n/a	n/a	6	9

Таблица 16: Запрос “nicolas cage movies”

target_trec_id	clueweb12-1704wb-36-10607
experiments	1	1	0	0	1	0	1	1	0	0
path_length	3	2	n/a	n/a	7	n/a	4	8	n/a	n/a

Таблица 17: Запрос “kids earth day activities”

target_trec_id	clueweb12-1700tw-16-18413
experiments	0	0	0	0	1	1	1	0	0	0
path_length	n/a	n/a	n/a	n/a	5	3	2	n/a	n/a	n/a

Таблица 18: Запрос “solar water fountains”

target_trec_id	clueweb12-0300tw-33-01415
experiments	1	0	0	1	1	1	0	0	1	0
path_length	3	n/a	n/a	1	1	2	n/a	n/a	6	n/a

Таблица 19: Запрос “what was the name of elvis presley's home”

target_trec_id	clueweb12-1904wb-94-13134
experiments	1	1	1	1	0	0	0	0	0	0
path_length	3	7	2	4	n/a	n/a	n/a	n/a	n/a	n/a

Таблица 20: Запрос “nba records”

target_trec_id	clueweb12-0305wb-53-32473
experiments	1	1	0	1	1	1	0	0	1	0
path_length	2	1	n/a	6	5	9	n/a	n/a	8	n/a

Таблица 21: Запрос “electoral college 2008 results”

target_trec_id	clueweb12-0102wb-31-05031
experiments	1	0	1	0	0	1	1	0	0	0
path_length	2	n/a	1	n/a	n/a	8	7	n/a	n/a	n/a

Таблица 22: Запрос “male menopause”

target_trec_id	clueweb12-0509wb-14-10674
experiments	0	0	1	1	0	0	0	1	1	1
path_length	n/a	n/a	3	5	n/a	n/a	n/a	2	4	9

Таблица 23: Запрос “usda food pyramid”

target_trec_id	clueweb12-0112wb-09-15320
experiments	1	1	0	0	1	1	0	1	0	0
path_length	2	4	n/a	n/a	3	5	n/a	6	n/a	n/a

Таблица 24: Запрос “ making chicken soup from scratch ”

target_trec_id	clueweb12-1504wb-87-23052
experiments	0	0	0	1	1	1	0	0	0	0
path_length	n/a	n/a	n/a	7	6	1	n/a	n/a	n/a	n/a

Таблица 25: Запрос “black and gold”

target_trec_id	clueweb12-1901wb-47-03420
experiments	1	1	0	0	0	1	1	1	0	0
path_length	3	5	n/a	n/a	n/a	6	4	8	n/a	n/a

Таблица 26: Запрос “traverse city”

target_trec_id	clueweb12-0001wb-40-32929
experiments	1	1	1	0	0	0	1	1	1	0
path_length	4	7	2	n/a	n/a	n/a	5	9	3	n/a

Таблица 27: Запрос “i will survive lyrics”

target_trec_id	clueweb12-1613wb-07-32091
experiments	0	0	0	0	1	1	1	0	1	1
path_length	n/a	n/a	n/a	n/a	5	3	2	n/a	7	4

Таблица 28: Запрос “hawaiian volcano observatories”

target_trec_id	clueweb12-1716wb-60-23030
experiments	1	1	1	1	0	0	0	1	1	0
path_length	1	4	2	6	n/a	n/a	n/a	5	3	n/a

Таблица 29: Запрос “beef stroganoff recipe”

target_trec_id	clueweb12-0008wb-61-17801
experiments	1	0	0	1	1	1	0	0	1	1
path_length	2	n/a	n/a	7	5	3	n/a	n/a	3	6

Таблица 30: Запрос “world's biggest dog”

target_trec_id	clueweb12-1415wb-74-08061
experiments	1	1	1	0	0	0	1	0	0	0
path_length	9	3	2	n/a	n/a	n/a	4	n/a	n/a	n/a

Таблица 31: Запрос “what are the seven deadly sins”

target_trec_id	clueweb12-1603wb-00-09641
experiments	1	1	1	1	0	0	0	0	0	0
path_length	8	7	4	9	n/a	n/a	n/a	n/a	n/a	n/a

Таблица 32: Запрос “hurricane Irene flooding in manville, nj”

target_trec_id	clueweb12-0715wb-81-29281
experiments	0	1	1	1	0	0	1	0	1	1
path_length	n/a	9	3	2	n/a	n/a	4	n/a	8	7

Таблица 33: Запрос “hair dye”

target_trec_id	clueweb12-0012wb-93-02071
experiments	1	0	0	1	1	1	0	1	0	0
path_length	1	n/a	n/a	4	6	3	n/a	7	n/a	n/a

Таблица 34: Запрос “dark chocolate health benefits”

target_trec_id	clueweb12-0506wb-00-27596
experiments	1	1	1	1	0	0	0	0	1	0
path_length	5	4	2	8	n/a	n/a	n/a	n/a	1	n/a



Таблица 35: Запрос “ham radio”

target_trec_id	clueweb12-1815wb-38-01274
experiments	0	1	1	1	1	1	0	0	0	0
path_length	n/a	3	5	7	8	4	n/a	n/a	n/a	n/a

Таблица 36: Запрос “symptoms of mad cow disease in humans”

target_trec_id	clueweb12-1409wb-00-13961
experiments	1	1	0	0	1	1	1	0	1	0
path_length	2	5	n/a	n/a	4	9	2	n/a	3	n/a

Таблица 37: Запрос “lump in throat”

target_trec_id	clueweb12-0012wb-45-00461
experiments	1	1	0	0	1	1	1	0	1	0
path_length	3	5	n/a	n/a	2	6	7	n/a	3	n/a

Таблица 38: Запрос “george bush sr bio”

target_trec_id	clueweb12-1010wb-87-07903
experiments	0	1	0	0	0	1	0	0	1	0
path_length	n/a	7	n/a	n/a	n/a	2	n/a	n/a	3	n/a

Таблица 39: Запрос “frank lloyd wright biography”

target_trec_id	clueweb12-0102wb-64-07634
experiments	1	1	0	0	0	1	1	0	1	1
path_length	5	3	n/a	n/a	n/a	1	7	n/a	3	2

Таблица 40: Запрос “presidential middle names”

target_trec_id	clueweb12-1714wb-62-05205
experiments	1	0	0	1	0	1	0	0	1	1
path_length	2	n/a	n/a	2	n/a	6	n/a	n/a	7	1

Таблица 41: Запрос “what is a wiki”

target_trec_id	clueweb12-0406wb-34-24341
experiments	1	1	1	1	0	1	1	0	0	1
path_length	2	4	3	5	n/a	1	n/a	n/a	n/a	1

Таблица 42: Запрос “cannellini beans”

target_trec_id	clueweb12-0607wb-37-05719
experiments	1	1	1	1	0	0	0	0	1	0
path_length	1	3	8	7	n/a	n/a	n/a	n/a	2	n/a

Таблица 43: Запрос “cannellini beans”

target_trec_id	clueweb12-0300wb-63-02268
experiments	1	1	1	1	0	0	0	0	1	0
path_length	9	7	2	3	n/a	n/a	n/a	n/a	4	n/a

Таблица 44: Запрос “old town Scottsdale”

target_trec_id	clueweb12-0916wb-56-30229
experiments	0	0	0	1	1	1	0	0	0	0
path_length	n/a	n/a	n/a	4	6	2	n/a	n/a	n/a	n/a

Таблица 45: Запрос “roosevelt island”

target_trec_id	clueweb12-0109wb-93-14385
experiments	0	1	0	1	0	1	0	1	1	0
path_length	n/a	7	n/a	2	n/a	5	n/a	3	2	n/a

Таблица 46: Запрос “civil war battles in south Carolina”

target_trec_id	clueweb12-0406wb-97-04957
experiments	1	1	0	0	1	1	1	0	0	1
path_length	3	5	n/a	n/a	9	7	2	n/a	n/a	1

Таблица 47: Запрос “rain man”

target_trec_id	clueweb12-1504wb-75-12379
experiments	0	1	0	0	0	0	1	1	1	1
path_length	n/a	5	n/a	n/a	n/a	7	2	3	8	1

Таблица 48: Запрос “eggs shelf life”

target_trec_id	clueweb12-0204wb-38-15238
experiments	1	1	1	0	0	0	1	0	0	0
path_length	1	3	6	n/a	n/a	n/a	4	n/a	n/a	n/a

Таблица 49: Запрос “ occupational therapist ”

target_trec_id	clueweb12-1803wb-06-12110
experiments	1	1	0	0	0	1	1	0	1	0
path_length	2	7	n/a	n/a	n/a	4	2	n/a	3	n/a

Таблица 50: Запрос “ford edge problems ”

target_trec_id	clueweb12-0000wb-17-09638
experiments	0	1	1	1	0	0	0	0	0	0
path_length	n/a	4	2	3	n/a	n/a	n/a	n/a	n/a	n/a

Таблица 51: Запрос “identifying spider bites ”

target_trec_id	clueweb12-0109wb-20-20925
experiments	0	0	0	1	1	0	0	0	1	0
path_length	n/a	n/a	n/a	7	3	n/a	n/a	n/a	4	n/a

Таблица 52: Запрос “history of orcas island”

target_trec_id	clueweb12-0818wb-81-06717
experiments	1	1	0	1	0	1	1	0	1	0
path_length	3	1	n/a	2	n/a	2	4	n/a	4	n/a

Таблица 53: Запрос “tooth abscess”

target_trec_id	clueweb12-1207wb-00-20715
experiments	1	1	0	0	0	1	1	1	0	1
path_length	3	4	n/a	n/a	n/a	3	5	8	n/a	6

Таблица 54: Запрос “barrett's esophagus”

target_trec_id	clueweb12-0911wb-52-13620
experiments	1	1	0	0	0	1	1	1	1	1
path_length	1	2	n/a	n/a	n/a	10	1	3	9	7

Таблица 55: Запрос “teddy bears”

target_trec_id	clueweb12-0012wb-38-00083
experiments	1	1	1	1	0	0	0	0	0	0
path_length	5	9	4	3	n/a	n/a	n/a	n/a	n/a	n/a

Таблица 56: Запрос “patron saint of mental illness”

target_trec_id	clueweb12-1513wb-11-16127
experiments	1	1	1	1	0	0	0	1	0	0
path_length	3	7	2	9	n/a	n/a	n/a	6	n/a	n/a

Таблица 57: Запрос “holes by louis sachar”

target_trec_id	clueweb12-1407wb-08-08201
experiments	0	0	1	1	1	0	1	1	0	0
path_length	n/a	n/a	3	5	7	n/a	8	2	n/a	n/a

Таблица 58: Запрос “hip roof”

target_trec_id	clueweb12-0005wb-79-05629
experiments	1	0	1	1	0	0	0	0	1	0
path_length	1	n/a	3	1	n/a	n/a	n/a	n/a	4	n/a

Таблица 59: Запрос “carpenter bee”

target_trec_id	clueweb12-1601wb-42-00581
experiments	1	0	1	0	0	0	0	0	1	0
path_length	1	n/a	3	n/a	n/a	n/a	n/a	n/a	4	n/a

Таблица 60: Запрос “the american revolutionary”

target_trec_id	clueweb12-1902wb-69-19121
experiments	0	0	1	1	0	0	0	1	1	0
path_length	n/a	n/a	3	7	n/a	n/a	n/a	4	1	n/a

Таблица 61: Запрос “folk remedies sore throat”

target_trec_id	clueweb12-0611wb-52-12698
experiments	1	1	1	1	0	0	0	0	1	0
path_length	5	9	10	3	n/a	n/a	n/a	n/a	2	n/a

Таблица 62: Запрос “balding cure”

target_trec_id	clueweb12-0600tw-12-11381
experiments	0	1	1	0	1	1	1	0	0	0
path_length	n/a	3	2	n/a	3	4	7	n/a	n/a	n/a

Таблица 63: Запрос “evidence for evolution”

target_trec_id	clueweb12-0008wb-13-06917
experiments	1	1	1	0	1	1	0	1	1	1
path_length	4	3	5	n/a	2	6	n/a	8	9	11

Таблица 64: Запрос “tribe formerly living in alabama”

target_trec_id	clueweb12-0109wb-16-18750
experiments	1	1	1	0	1	1	0	0	0	0
path_length	3	1	7	n/a	8	9	n/a	n/a	n/a	n/a

Таблица 65: Запрос “F5 tornado”

target_trec_id	clueweb12-0205wb-90-26069
experiments	0	1	0	0	1	1	0	1	0	0
path_length	n/a	8	n/a	n/a	2	3	n/a	1	n/a	n/a

Таблица 66: Запрос “symptoms of heart attack”

target_trec_id	clueweb12-0003wb-56-28161
experiments	0	1	1	1	1	1	0	1	0	0
path_length	n/a	2	5	7	3	1	n/a	2	n/a	n/a

Таблица 67: Запрос “feliz navidad lyrics”

target_trec_id	clueweb12-0012wb-10-29307
experiments	0	0	0	1	1	1	0	0	0	0
path_length	n/a	n/a	n/a	4	9	6	n/a	n/a	n/a	n/a

Таблица 68: Запрос “ benefits of running ”

target_trec_id	clueweb12-1806wb-14-09041
experiments	1	0	0	1	1	1	1	0	0	0
path_length	7	n/a	n/a	1	5	6	3	n/a	n/a	n/a

Таблица 69: Запрос “marshall county schools”

target_trec_id	clueweb12-0013wb-74-12183
experiments	1	0	0	1	0	1	1	0	1	0
path_length	2	n/a	n/a	3	n/a	8	4	n/a	1	n/a

Таблица 70: Запрос “sun tzu”

target_trec_id	clueweb12-0109wb-62-20400
experiments	1	0	0	0	0	0	0	0	1	0
path_length	10	n/a	n/a	n/a	n/a	n/a	n/a	n/a	3	n/a

Таблица 71: Запрос “halloween activites for middle school”

target_trec_id	clueweb12-0207wb-30-15840
experiments	1	0	0	1	0	0	1	0	0	0
path_length	9	n/a	n/a	10	n/a	n/a	4	n/a	n/a	n/a

Таблица 72: Запрос “dreams interpretation”

target_trec_id	clueweb12-0110wb-40-30641
experiments	1	0	0	1	1	0	1	1	0	1
path_length	6	n/a	n/a	5	4	n/a	2	7	n/a	3

Таблица 73: Запрос “wilson's disease”

target_trec_id	clueweb12-1012wb-52-12726
experiments	1	1	0	1	0	0	1	0	0	0
path_length	3	4	n/a	2	n/a	n/a	5	n/a	n/a	n/a

Таблица 74: Запрос “golf instruction”

target_trec_id	clueweb12-0012wb-50-06846
experiments	1	0	0	1	0	1	1	1	1	1
path_length	7	n/a	n/a	5	n/a	6	8	7	2	3

Таблица 75: Запрос “uss cole”

target_trec_id	clueweb12-1617wb-28-07000
experiments	0	0	0	1	1	1	1	1	1	1
path_length	n/a	n/a	n/a	3	2	4	1	1	3	5

Таблица 76 Запрос “how has african american music influence history”

target_trec_id	clueweb12-1610wb-30-09638
experiments	1	0	0	1	1	1	0	0	0	1
path_length	9	n/a	n/a	7	3	5	n/a	n/a	n/a	5

Таблица 77 Запрос “bewitched cast”

target_trec_id	clueweb12-0301tw-21-07830
experiments	0	0	0	1	1	1	0	0	0	1
path_length	n/a	n/a	n/a	2	7	5	n/a	n/a	n/a	9

Таблица 78 Запрос “mister rogers”

target_trec_id	clueweb12-1804wb-22-22837
experiments	0	0	1	1	1	1	0	0	0	1
path_length	n/a	n/a	3	5	1	6	n/a	n/a	n/a	2

Таблица 79 Запрос “game theory”

target_trec_id	clueweb12-1306wb-02-02797
experiments	1	0	1	1	1	1	0	0	1	0
path_length	2	n/a	4	6	7	8	n/a	n/a	1	n/a

Таблица 80 Запрос “view my internet history”

target_trec_id	clueweb12-1808wb-11-27687
experiments	0	0	1	1	1	1	0	0	1	0
path_length	n/a	n/a	3	2	1	5	n/a	n/a	2	n/a

Таблица 81 Запрос “ketogenic diet”

target_trec_id	clueweb12-0900tw-23-13239
experiments	0	0	1	1	1	1	1	0	1	0
path_length	n/a	n/a	4	5	6	7	11	n/a	8	n/a

Таблица 82 Запрос “nasa interplanetary missions”

target_trec_id	clueweb12-0406wb-01-13228
experiments	0	0	0	1	1	1	1	0	1	0
path_length	n/a	n/a	n/a	3	2	9	1	n/a	2	n/a

Таблица 83 Запрос “hairdyes in pa”

target_trec_id	clueweb12-0010wb-73-33727
experiments	1	0	0	1	1	1	1	0	1	0
path_length	7	n/a	n/a	6	5	1	4	n/a	3	n/a

Таблица 84 Запрос “where to find morel mushrooms”

target_trec_id	clueweb12-1906wb-58-21953
experiments	1	0	0	1	1	1	0	0	1	1
path_length	2	n/a	n/a	5	4	3	n/a	n/a	3	6

Таблица 85 Запрос “magnesium rich foods”

target_trec_id	clueweb12-0202wb-27-20014
experiments	0	0	0	1	1	1	0	0	0	0
path_length	n/a	n/a	n/a	3	2	9	n/a	n/a	n/a	n/a

Таблица 86 Запрос “common schizophrenia drugs”

target_trec_id	clueweb12-0000wb-59-16108
experiments	0	1	0	1	1	1	0	0	0	0
path_length	n/a	3	n/a	3	9	4	n/a	n/a	n/a	n/a

Таблица 87 Запрос “common schizophrenia drugs”

target_trec_id	clueweb12-0310wb-48-08260
experiments	0	0	0	0	1	1	0	1	1	0
path_length	n/a	n/a	n/a	n/a	7	2	n/a	5	3	n/a

Таблица 88 Запрос “fidel castro”

target_trec_id	clueweb12-0603wb-15-04224
experiments	1	1	0	0	0	1	0	0	1	1
path_length	3	1	n/a	n/a	n/a	4	n/a	n/a	3	6

Таблица 89 Запрос “benefits of yoga”

target_trec_id	clueweb12-0709wb-58-09485
experiments	1	1	0	0	0	0	0	0	0	1
path_length	8	6	n/a	n/a	n/a	n/a	n/a	n/a	n/a	10

Таблица 90 Запрос “norway spruce”

target_trec_id	clueweb12-0903wb-43-10438
experiments	1	1	1	0	0	1	0	0	0	0
path_length	7	2	5	n/a	n/a	6	n/a	n/a	n/a	n/a

Таблица 91 Запрос “sangre de cristo mountains”

target_trec_id	clueweb12-0008wb-98-03105
experiments	1	0	1	0	0	1	0	1	0	0
path_length	1	n/a	3	n/a	n/a	6	n/a	4	n/a	n/a

Таблица 92 Запрос “history of electronic medical record”

target_trec_id	clueweb12-1400tw-47-14197
experiments	1	0	1	0	0	1	1	1	0	0
path_length	1	n/a	5	n/a	n/a	3	2	7	n/a	n/a

Таблица 93 Запрос “educational advantage of social networking sites”

target_trec_id	clueweb12-1106tw-31-19353
experiments	0	0	1	0	0	1	1	0	1	1
path_length	n/a	n/a	3	n/a	n/a	5	2	n/a	4	6

Таблица 94 Запрос “flowering plants”

target_trec_id	clueweb12-0221wb-34-06570
experiments	0	0	0	0	0	1	1	0	1	1
path_length	n/a	n/a	n/a	n/a	n/a	7	4	n/a	9	1

Таблица 95 Запрос “how to tie a windsor knot”

target_trec_id	clueweb12-0800tw-44-07181
experiments	0	1	0	1	0	1	1	0	1	1
path_length	n/a	1	n/a	6	n/a	3	2	n/a	8	7

Таблица 96 Запрос “recycling lead acid batteries”

target_trec_id	clueweb12-1207wb-56-13781
experiments	1	1	1	0	1	1	1	0	0	1
path_length	2	6	9	n/a	4	9	3	n/a	n/a	1

Таблица 97 Запрос “altitude sickness”

target_trec_id	clueweb12-0010wb-21-01455
experiments	0	1	0	0	1	1	1	0	1	0
path_length	n/a	8	n/a	n/a	3	7	4	n/a	2	n/a

Таблица 98 Запрос “medical care and jenovah's witnesses”

target_trec_id	clueweb12-0204wb-88-10488
experiments	1	1	0	0	1	1	1	0	1	1
path_length	7	2	n/a	n/a	5	2	6	n/a	3	7

Таблица 99 Запрос “pink slime in ground beef”

target_trec_id	clueweb12-1500tw-96-00983
experiments	1	0	0	0	0	0	1	0	1	0
path_length	2	n/a	n/a	n/a	n/a	n/a	9	n/a	9	n/a

Таблица 100 Запрос “how to find the mean”

target_trec_id	clueweb12-0408wb-68-23066
experiments	1	0	1	0	1	1	1	0	1	0
path_length	2	n/a	4	n/a	7	8	3	n/a	5	n/a



Выводы

В результате выполнения работы была произведена обработка исходных данных коллекции ClueWeb12_B13, были извлечены страницы, каждая из которых была преобразована в Term Frequency Vector. Далее была произведена имплементация алгоритма локального поиска на полученной структуре данных сети Интернет. Ниже приведена таблица с процентом успеха поиска и средней длиной пути по каждому запросу:

TREC topic number	Success	Average path length
201	40%	4
202	30%	4
203	50%	3,8
204	60%	4,2
205	30%	3,7
206	20%	5
207	80%	4,4
208	50%	3,2
209	40%	5,5
210	40%	4
211	50%	5,4
212	40%	5,25
213	50%	3,4
214	50%	4,8
215	40%	5,25
216	50%	4,8
217	30%	3,3
218	50%	2,6
219	40%	4
220	60%	5,2
221	40%	4,5
222	50%	4,6
223	50%	4
224	30%	4,7
225	50%	5,2
226	60%	5
227	50%	4,2
228	60%	3,5
229	60%	4,3
230	40%	4
231	40%	5,75
232	60%	5,5
233	50%	4,2
234	50%	4
235	50%	5,4
236	60%	4,2
237	60%	3,2
238	30%	4
239	60%	3,5
240	50%	3,6
241	70%	2,3
242	50%	4,2
243	50%	5
244	30%	4
245	50%	3,8
246	60%	4,5
247	50%	5,2
248	40%	3,5
249	50%	3,6
250	30%	3
251	30%	4,6
252	60%	2,6
253	60%	4,8
254	70%	4,7
255	40%	5,25
256	50%	5,4
257	50%	5
258	40%	2,25
259	30%	2,7
260	40%	3,75
261	50%	5,8
262	50%	3,8
263	80%	6
264	50%	5,6
265	40%	3,5
266	60%	3,3
267	30%	6,3
268	50%	4,4
269	50%	3,6
270	20%	6,5
271	30%	7,7
272	50%	5,4
273	40%	3,5
274	70%	5,4
275	70%	2,7
276	50%	5,8
277	40%	5,8
278	50%	3,4
279	60%	4,7
280	50%	2,6
281	60%	5,5
282	50%	3,4
283	60%	4,3
284	60%	3,8
285	30%	4,6
286	40%	4,75
287	40%	4,25
288	50%	3,4
289	30%	8
290	40%	5
291	40%	3,5
292	50%	3,6
293	50%	4
294	40%	5,25
295	60%	4,5
296	50%	4,2
297	50%	3,8
298	70%	4,5
299	30%	6,7
300	60%	4,7

Результаты поиска, представленные выше, не отличаются высокими показателями успеха. Средний процент успеха по запросам составляет около 48%. Средняя длина пути от стартовой вершины до искомой составляет приблизительно 4,4. Причиной такого процента успеха могут служить целый ряд факторов. В данном алгоритме используется лишь локальная информация, в нашем случае это ресурсы - “соседи” по Веб-графу. И от выбора начальной вершины напрямую зависит успех поиска. Первоначально, в экспериментах по поиску заданного ресурса стартовая вершина выбирались абсолютно случайно, и от этого сильно страдало качество результатов. Поэтому в дальнейшем была введена проверка- значение по косинусной мере должна быть выше нуля, в противном случае гарантия успеха стремится к нулю. Это значит, что стартовая страница должна иметь хоть какое-то отношение к задаваемому запросу.

Также причиной может служить ограниченность выборки- 7% от всего датасета ClueWeb12. При поиске вершин-соседей в Веб-графе, некоторые пути отклоняются (до 23%) в силу невозможности их проверки по косинусной мере. Это может ограничить потенциальные пути к искомой вершине, однако по причине того, что соответствующие ресурсы не были преобразованы в формат tf-idf, их невозможно проверить на релевантность по отношению к запросу. Среднее время поиска составляет 3,30 - 4 минуты. Такие результаты быстродействия напрямую связаны с размером Веб- графа, время его загрузки на доступной конфигурации составляет 2 минуты 50 секунд, остальное время уходит на поиск заданной страницы.

В идеальной ситуации считалось бы достаточным иметь набор Term Frequency Vectors, и программе нужно было лишь “опрашивать” соседей на предмет вхождения слов из запроса в страницу, однако на практике такого набора данных оказывается недостаточно. Если не задавать конечную вершину, а просто выдавать на каждой итерации наилучший результат, то данный алгоритм имеет право на осуществление поиска по структуре Веб.



Литература

http://www.lemurproject.org/clueweb12/specs.php

Milgram, Stanley (May 1967). "The Small World Problem". Psychology Today (Ziff-Davis Publishing Company.).

Manning, C. D.; Raghavan, P.; Schutze, H. (2008). "Scoring, term weighting, and the vector space model". Introduction to Information Retrieval (PDF). p. 100. doi:10.1017/CBO9780511809071.007. ISBN 9780511809071

Wu, H. C.; Luk, R. W. P.; Wong, K. F.; Kwok, K. L. (2008). "Interpreting TF-IDF term weights as making relevance decisions". ACM Transactions on Information Systems 26 (3): 1. doi:10.1145/1361684.1361686

http://lucene.apache.org/core/3_6_1/api/all/org/apache/lucene/search/Similarity.html

Paolo Boldi and Sebastiano Vigna. The WebGraph framework I: Compression techniques. In Proc. of the Thirteenth International World Wide Web Conference (WWW 2004), pages 595?601, Manhattan, USA, 2004. ACM Press.

Размещено на Allbest.ru