Мета поиск

Страница 1

Метапоисковые через совместное цитата график

Хен Чул Ли

Факультет компьютерных наук

Университет Торонто

Торонто, Онтарио, M5S3G4

leehyun@cs.toronto.edu

Аннотация Несмотря на многочисленные поисковые доступны на

Интернет, ни один двигатель способен выполнять "лучше" в

любых обстоятельствах. Это не так, метапоиска двигателей

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

слияние проблема: данный рейтинг списков страниц возвращается

нескольких поисковых системах в ответ на данный запрос, что является

Лучший способ объединить эти списки в один список? В этой статье мы

представить алгоритм, основанный на совместной цитата график построен

из поисковых систем и вернулся списков страниц справиться с этой

вопрос. Наш алгоритм может быть реализован в простой и наивный

образом в то время как на основе строгого и интуитивно лечение

проблемы. В отличие от тех методов, которые опираются на соответствующие оценки

страниц, наш алгоритм может быть реализован только с помощью ранг

информации.

Ключевые слова слияние, reranking, мета-поиск

I. ВВЕДЕНИЕ

В настоящее время число доступных поисковых систем является кон-

Последовательность тот факт, что ни одна поисковая способен

собрать все данные в Интернете и держать их до разумных

даты. Чтобы преодолеть эту ситуацию, метапоиска двигателей (например,

как изобилие, savvysearch, Ixquick, Vivisimo, Metacrawler)

Были введены предоставление унифицированного доступа к нескольким

существующих поисковых систем: они передают запрос в соответствующие

, лежащих в основе поисковых машин, объединить вернулся списков страниц

в единый список, а также представит новый рейтинг список пользователей. Один

важным вопросом в метапоиска конструкции двигателя является слияние

[3], [4], [6], [11], [12], как правило, известные в литературе или

ранг агрегации [1], то есть, как слияние или совокупность

вернулся рейтинг списков страниц в единый ранжированный список.

слияние проблема возникает во многих областях, включая ИК-порт, база данных

и теории социального выбора. В этой статье, однако, мы имеем в виду любой

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

элемент в этом ранжированный список, как страница с метапоиска из

веб-страницы является одним конкретным приложением, что мы рассматриваем

в этой статье. Различные методы объединения были предложены

но в основном все рассмотреть следующие два аспекта:

1) Качество поисковых систем: некоторые методы слияния делать

не относиться в равной степени во всех поисковых системах, но они "дискриминацией

SHS входит "среди поисковых систем [12] в зависимости от

Качество страниц, которые они производят. Кроме того, это полезно

знать качество поисковых систем, потому что, зная

качество поисковых систем по отношению к определенному

задача априори, мы можем сэкономить ресурсы отправки запроса

на лучший набор поисковых системах только. Таким образом, различные

эвристики и методов, которые используются для определения качества

поисковые системы [3]. Большинство методов использовать точность

поисковых систем, что является достаточно субъективной особенно

в контексте добычи Интернете.

2) Качество страниц: кроме звания информации страниц,

некоторые слияния методы использовать актуальность десятки

страницы относительно запроса. Если актуальность баллы

можно получить в поисковых системах, а затем эти баллы

используется, но если они не доступны, то актуальность

десятки страниц получены через некоторый тип

Контент-анализ [6] или звания информация используется в качестве

актуальность счет. Чтобы определить окончательный счет

документ, большинство методов использования некоторая линейная комбинация

соответствующие оценки страниц [11], [15], [14], [6].

В этой статье мы предлагаем совместно цитата модель, которая лечит

Проблема объединения как набор экспертов (поисковые системы)

предоставление мнения (рангов) о различных вариантов (страниц), что

могут иметь отношение к запросу. На основе этой модели, мы

представлен алгоритм, который похож по духу популярной

алгоритм анализа ссылок популярности [8].

Сообщается, например, Ли [5] в отношении к

CombMNZ алгоритм, что "различные трассы получить аналогичные наборы

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

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

лучшие результаты слияния, если вес больше общих документов

степени, чем те, которые таковыми не являются. В настоящее время большинство поисковых систем

использовать собственные передовые методы ранжирования (анализ и ссылка

контент-анализ) 1 до получить наиболее релевантные документы

для запроса, так что мы считаем, что ранг информации достаточно

объединить списки рейтинга веб-страниц. Кроме того, во многих

реальном мире ситуаций, релевантности страниц не

доступна. Таким образом, наша метапоиска алгоритм использует только

на звание информации вернулся в поисковых системах. Наши

метапоиска Алгоритм основан на следующих взаимных Рейн-

нительных отношений: "хорошая страница (власти), что является одним

является высоко оценены многими хорошими поисковыми системами (центров), а

хороший поисковый (центр) является одним, который занимает очень много

хороший страницы (власти) ". Используя это соотношение, алго-

ритма поддерживает и обновляет численный вес многократно.

Этот алгоритм не только решает задачу объединения, но это

также обеспечивает основу для оценки качества поиска

Двигатели на объективной основе. Остальная часть этой работы

организована следующим образом: раздел 2 представляет работы, связанной с раздела

1Therefore, поисковые системы "экспертов" и их "мнение" должно быть

считается очень ценным, чем давать наше «мнения» о

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

Страница 2

3 дает подробное описание нашего метода, раздел 4 подарков

некоторые эксперименты с нашим алгоритмом и обсуждаются результаты

получены, и, наконец, раздел 5 кратко нашей работы представляет

выводы и предложения для будущих исследований.

II. СВЯЗАННЫЕ РАБОТЫ

A. Предыдущие работы, касающиеся проблемы объединения

В этом разделе мы представляем некоторые из предыдущих методов

использовать для решения проблемы объединения.

1) Линейная модель Комбинация: Один из самых простых и

Наиболее популярным методом является линейная модель комбинации

(LCM), которая сочетает в себе линейной нормированной актуальность

баллы присваиваются каждой странице по составляющим поиск

двигателей. То есть относительная (р) =

II отн я (р), где я это вес

уделяется каждой поисковой системы, а также относительная

я () является оценка значимости

части страницы. Сумма берется по всем учредительных поиск

двигателей.

2) CombANZ, CombSUM, CombMNZ: Предложен Fox

и Шоу [7], этот алгоритм относится ко всем поисковым системам, как равный,

и решает проблемы объединения на основе невзвешенных мин

или максимум или средняя сумма нормированных значимость каждой страницы

баллы по составляющим поисковых системах. То есть относительная (р) =

п. р

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

, которые вернулись на странице и

2 F 1, 0, 1 г. Сумма берется по

всех субъектах поисковых системах. Если = 1, то система

называется "CombANZ", что эквивалентно средней

Сходство на поисковые системы, которые возвращаются с. Если = 0,

Система называется "CombSUM", которая эквивалентна

Сумма общего. Наконец, когда = 1, то система называется

"CombMNZ".

3) Броды-предохранителя и взвешенный Броды-предохранитель: Предложено

Аслам и Монтегю [4] 2, этот алгоритм основан на

Борда подсчета голосов алгоритм, который широко изучен

В социальной общности теории выбора. Счет страницу

это просто сумма рангов вернулся учредительными поиск

двигателей. То есть оценка (р) =

забить я (р), где забить я ()

обозначает точки назначенные странице я в соответствии с его

ранг в каждой поисковой системе, то есть для каждой поисковой системы,

высокий рейтинг страницы дается некоторый произвольный с

0 очков,

второй ранг страницы дается с-1 точек, и так далее. Если есть

Некоторые страницы оставили неранжированного с помощью поисковой системы, а остальные

Точки равномерно распределены между неранжированного страниц. Взвешенный

Борда-Fuse является разновидностью Броды-Fuse, где ранги

взвешенных по десятков поисковых системах. То есть оценка (р) =

я я ранге я (р), где я это вес присваивается каждому поиск

двигателя.

B. Со-цитата график для анализа ссылок

Использование совместно цитата график не является новой. Это был

широко используется (например, социальные сети и библиометрических), но

Недавнее введение HITS алгоритм анализа ссылок

веб-страниц росту научно-исследовательскую деятельность в этой области. Предложенный

по Клейнберг [8], хитов первый алгоритм анализа использовались ссылки

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

2А немного другой версии, предложенной в [6]

Набор страниц, состоящий из короткого списка веб-страниц вернулся

с помощью поисковой системы. Позднее этот корневой набор дополнен

страницы, на которую указывает страниц в корневую, а также

на страницы, которые указывают на страницы в корневой набор для формирования более широкого набора

называемый базовый набор, который делает запрос попадает в зависимость методом.

Далее, учитывая базовый набор, "авторитет" вес страницы

рассчитывается с "центром" веса страниц, которые указывают на

страницы, и "хаб" вес страницы рассчитывается по

"Авторитет" веса страниц, на который указывает на страницу.

Точнее, учитывая базовый набор, который состоит из N страниц, HITS

является матрицей смежности размером N

N, где IJ = 1

если есть ссылка с я к у и 0 в противном случае. Далее, он присваивает

каждой странице я власть веса я и вес центром ч я, то

уравнений

( т +1)

у ! я ч

( т )

J , ч

( т +1)

я ! к

( т )

А это

до повторного

( т )

я и ч

( т )

я сходятся к неподвижной точке

я и

ч я соответственно (с векторами перенормированная на единицу длины

на каждой итерации).

III. СЛИЯНИЕ ПРОБЛЕМА

А. Описание проблемы

Мы формально описать общую задачу объединения, где

Проблема объединения в контексте веб-одна

Конкретный пример, что мы заинтересованы Учитывая Вселенной

U и лица я, упорядоченный список (или простой список) по

на U, которая обозначается T

я = [т я 1

т я 2

:::

т я н ], является

упорядочения подмножество Q

U размер № 3, с каждым т

я J 2 Q, и

некоторое отношение порядка на Q. Пусть S множество к ан

, где каждый объект представляет собой список, и пусть Т = Т Т

1 , Т 2 ; ::: Т к г

множество к упорядоченных списков производится членов о

я каждый 2 S, пусть ранг

я : T я ! [0, 1] не убывает

функции (если р

д, то оценить

я (т я р )

ранг я (т я д )), что

у 2 т я

ранг я (т я у ) = 1. Пусть R = F ранг

1 ::: ранг к г будет

набор весовых функций ранга Т. Хотя EAC

Двигатель я могу иметь свое взвешенное функция ранга, в го

будем считать, что весовых функций ранга др.

Двигатели равны, то будет один weighte

Функция ранга, что ранг = звание

я для всех. Учитывая (S, T, R)

в качестве входных данных, слияние проблема то, чтобы найти "оптимальный" список

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

Смысл "оптимальный" зависит от нескольких критериев, и

Особенно трудно в контексте веб-формализовать

Понятие "оптимальный". Феджин и соавт. [2] имеют дело с этими критериями

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

списки.

B. Со-цитата график

Учитывая (S, T, R), А = [ J T J

я = 1 т я. Мы определяем совместно цитата

Граф , как граф CG = (V, E) такая, что V = S [и (р, д)

2 E, если р 2 S и ^ 2 , а вес присваивается каждому ребру

(Р, д) ранг р (д). Другими словами, CG является би-дольный граф

, где одна сторона состоит из всех поисковых систем и других

сторона состоит из объединения страниц вернулись в поисковых системах.

Там будут ссылки с р и д, если д страница находится в списке

3Note, что не существует ограничений на размер каждой T

я. В этой статье

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

Страница 3

Рис. 1. Пример 1

возвращается с поисковой системы и вес присваивается

ссылка соответствующих весовых ранг ранг р (д). Таким образом,

Матрица смежности этого графа , который будет обозначаться W,

матрица размером кн такой, что W рд = W ((р, д)) = звание

р (д)

если р ! д и W рд = 0 в противном случае.

Пример 1: При S = F с 1 , с 2 г, Т 1 = [а> Ь], T +2 =

[B> C] и взвешенная функция ранга, ранг 1 (а) =

ранг 2 (б) = 2 = 3, ранг 1 (б) = ранг 2 (а) = 1 = 3. Мы можем

построить совместно цитата график , как показано на рисунке 1 и

после матрицей смежности:

W =

} |

{

2 = 3 1 = 3

с 1

с 2

C. взвешенный HITS (WHITS)

Как было отмечено во введении, наша метапоиска

Алгоритм основан на взаимное усиление между

поисковых систем и страницы вернулись в поисковых системах. Данный

(S, T, R) в качестве вклада, пусть п (р) обозначает "хаб" счет поиска

Двигатель р, и пусть (д) обозначает "авторитет" счетом страницы ц.

Мы делаем следующее:

Построить из CG (S, T, R)

Инициализировать все полномочия оценки и центр оценки как 1

в то время как ( ( т )

и ч ( т )

сходится к неподвижной точке

и з)

0 ( т +1)

(Q) =

р ! д

ранг р (д) ч ( т ) (р) ( г )

час

0 ( т +1)

(Р) =

р ! д

ранг р (д) ( т ) (ц) ( г )

нормализация

0 ( т +1)

; Ч

0 ( т +1)

( т +1) =

0 ( т +1)

; Ч ( т +1) = Л

0 ( т +1)

Один объединенный список страниц, производится сортировка

страницы в соответствии с их полномочиями баллов. Мы называем

наш алгоритм взвешенного HITS или просто WHITS. Если мы обозначим

к ( т ) = (

( т )

1 ;

( т )

2 :::

( т )

л ) вектор власти веса

в момент времени т и ч ( т ) = (А

( т )

1 , ч

( т )

2 ::: ч

( т )

к ) вектор центра

вес в момент т, то соотношения ( у ) и ( г ) может быть

записать в матричной форме с помощью матрицы смежности Вт

совместно цитата график как

( т +1)

= W

час

( т )

= (W

( т )

час

( т +1)

= Wa

( т +1)

= (WW

) Ч

( т )

Таким образом, векторы

= ( 1 ::: N ) и ч

= (А 1 ; ::: ч к )

главные векторы W

W и мировой trespectively,

Таблица I

Перекрытие TOP 100 и 20 страниц

ТМ

0,2916

0,3287

0,3687

0,3651

0,0412

ТМ

0,2916

0,2396

0,2774

0,2532

0,0306

0,3287

0,2396

0,2764

0,2619

0,0335

0,3687

0,2774

0,2764

0,2851

0,0383

0,3651

0,2532

0,2619

0,2851

0,0461

0,0412

0,0306

0,0335

0,0383

0,0461

Перекрытие из 100 страниц

ТМ

0,3774

0,3516

0,4403

0,4983

0,0483

ТМ

0,3774

0,2580

0,3306

0,3548

0,0451

0,3516

0,2580

0,2741

0,3080

0,0387

0,4403

0,3306

0,2741

0,3983

0,0419

0,4983

0,3548

0,3080

0,3983

0,0403

0,0483

0,0451

0,0387

0,0419

0,0403

Перекрытие из 20 страниц

т.е. взвешенное HITS эквивалентно мощности методом

найти основные векторы W

W WW и т. Один

Легко доказать, что мы всегда можем найти такие собственные

помощи рассуждений, аналогичных приведенной в [16]. Размер

из W

W есть у [ к

я = 1 т я JJ [ к

я = 1 т я у, и размер WW

ТИС

у S J J S у. На практике, матриц применить эту

W и мировой таре небольшой

и, как правило, сходятся в несколько итераций, что делает

взвешенный HITS вычислительно недорого. Обратите внимание, что рядом

"авторитет" десятки страниц, алгоритм также выводит

"Хаб" десятки поисковых системах. Таким образом, наш взвешенный HITS может

также может быть использован для оценки "производительности" поисковых систем

(Репутация поисковых систем среди своих сверстников) в отношении

на запрос без использования точной скорости поисковых системах.

Такого рода информация может быть ценной, так как некоторые слияния

методы [11], [12] на основе такой информации. Следует

Следует отметить, что после совместного цитата график построен, мы можем

использовать взвешенный версию любой алгоритм анализа ссылок, например,

Порог-хиты, байесовский, сальса, и так далее (см. [10]), к

обрабатывать слияния. В самом деле, это не очень трудно видеть, что при

взвешенная версия SALSA [9] применяется на подключенный

совместно цитата график , он совпадает с Броды-Fuse метод.

IV. Экспериментальные результаты

В этом разделе мы представляем некоторые результаты различных экс-

Экспериментальные исследования, которые мы conducted4. Для наших целей мы

использовали 6 поисковых систем, Google (GL), Teoma (TM), Altavista (AT),

AllTheWeb (AL), Inktomi (IN) и northernlight (NL). Мы отправили 31

различные запросы, позитивные действия, алкоголизм, развлечения

парки, архитектура, езда на велосипеде, блюз, сыр, цитрусовые рощи

, Классическая гитара, компьютерное зрение, Долина Смерти, хоккей на траве,

садоводство, графический дизайн, ВИЧ, Java, Липари, болезнь Лайма,

паевые инвестиционные фонды, национальные парки, параллельной архитектурой, утилизация

банки, скалолазание, Сан - Франциско, Шекспир, штамп собирать-

ING, суши, настольный теннис, дистанционная, старинных автомобилей, дзен-бутон

dhism к каждой поисковой системе получения 100 страниц из каждой

один. Это была наша гипотеза, что должна существовать существенные

4These эксперименты проводились между январем и февралем 2003

Страница 4

Таблица II

Средние значения центром WHITS / FWHITS И ПОИСК

ДВИГАТЕЛЬ ЗВАНИЯ ЗА ВСЕ ВОПРОСЫ

Ср. центр веса

Поисковая ряды

0,2010

0,2234

0,0325

ТМ

0,1880

0,2047

0,1833

двигатель / 1-го ранга второго

Третья

Четвёртое

Пятый

Шестой

ТМ

FWHITS ( F + +

)

Ср. центр веса

Поисковая ряды

0,2530

0,0447

ТМ

0,2451

0,2543

0,2360

двигатель / ранг

Первый

Вторая

Третья

Четвёртое

Пятый

ТМ

FWHITS без Google ( F

г)

Ср. центр веса

Поисковая ряды

AL 0,2531

GL 0,2692

NL 0,0433

ТМ 0,2350

0,2325

двигатель / 1-го ранга 2nd 3rd четвёртый пятый

ТМ

FWHITS без Inktomi ( F

я)

Ср. центр веса

Поисковая ряды

AL 0,2006

GL 0,2230

NL 0,0328

ТМ 0,1887

0,2058

0,1822

двигатель / 1-го ранга 2nd 3rd четвёртый пятой шестой

ТМ

WHITS ( W

+ +

)

Ср. центр веса

Поисковая ряды

0,2529

0,0452

ТМ

0,2451

0,2553

0,2346

двигатель / ранг

Первый

Вторая

Третья

Четвёртое

Пятый

ТМ

WHITS без ( W

г)

Ср. центр веса

Поисковая ряды

AL 0,2539

GL 0,2667

NL 0,0438

ТМ 0,2362

0,2325

двигатель / 1-го ранга 2nd 3rd четвёртый пятый

ТМ

WHITS без Inktomi ( W

я)

ряд общих страниц. Таким образом, мы рассчитали средний-

возрастом количество перекрывающихся страниц из 100 и 20 страниц

проверить эту гипотезу, не используя сложные дублирование-

Кейт и нечетких дубликатов страниц поиска алгоритма [13], как показано

в таблице процент перекрытия из 100 страниц

вернулся на 6 поисковых систем является достаточно высоким, начиная от

0,2396 до 0,3687 с единственным исключением northernlight.

Процент перекрытия из 20 страниц, еще выше. Их

Процент перекрытия между 0,2580 и 0,4983 без

учитывая northernlight. Все со-цитирование графы за исключением тех,

contructed от «позитивных действий», «графический дизайн» и

«Взаимные фонды» оказались связные графы. Но, когда

northernlight не считается, все со-цитирование графы

установлено, что связано укрепление нашей веры, что на практике

Борда-Fuse метод на самом деле является взвешенным версия

SALSA. Далее, наш взвешенный HITS был реализован с помощью

Следующие 2 разных весовых функций ранга:

1) весовой функции звание дается г (г) = 2 (п

г (я) + 1) = (п (п + 1)), где г (г) = звание страницу.

Мы называем эту версию взвешенный хиты, как WHITS.

2) взвешенная функция звание дается г (я) = 2

S (I) = (р (р + 1)), где р = п = 20 и

с (я) =

>> <

>>:

п = 20

если я в топ 20 страниц

п = 20 1, если я в ближайшие 20 страниц

:::

если я в последних 20 страниц

Мы называем эту версию взвешенный хиты, как FWHITS.

Как отмечалось ранее, наш алгоритм может быть использован для

оценку в поисковых системах. Таким образом, мы сравнили центр

Репутация различных поисковых системах, используемых в наших экспериментах

как показано в Таблице II. Можно заметить, что центр репутации

в Google является самой высокой в то время как northernlight является самым низким для

как WHITS и FWHITS. Учитывая, сколько раз

, что поисковая система оценивается как лучшее, Google доминирует

другие поисковые системы рассматривается 23 (22) раз

лучшая поисковая система его сверстников. Кроме того, центр репутации

Двигатели поиска были рассчитаны на 2 разные настройки. 1)

WHITS и FWHITS без Google 2) WHITS и FWHITS

без Inktomi. Концентратор репутация поисковых систем по

их параметры также приведены в табл. Когда

Google не используется, AllTheWeb и Inktomi имеют самый высокий

центр веса следуют Teoma, Altavista и northernlight для

как WHITS и FWHITS. Когда Inktomi не используется, то

центр репутации Google является самым высоким затем AllTheWeb,

Teoma, Altavista и northernlight.

Для оценки производительности WHITS и FWHITS, мы

по сравнению производительности WHITS и FWHITS к

в Google. После тщательного изучения со страницами возвращаются

WHITS, FWHITS и Google, мы смогли заключить

что оба WHITS и FWHITS субъективно уступает

Google во многих запросов особенно, когда Google был спам.

Например, все топ 20 страниц возвращается FWHITS и

WHITS имеют отношение к запросу "садоводство", а Google

вернулся странице "http://www.sierra.com", который является страница

посвященный видеоиграм, как 2-й лучший страницу в свой список

20 лучших страниц. На запрос "сыр", Google вернулась

"Http://www.steakandcheese.com" в котором содержатся взрослые кон-

тентовый материал в то время как ни WHITS ни FWHITS вернулся этом

страницу в свои списки 60 лучших страниц. Для краткости мы

присутствует только результаты по запросам "Шекспир" и "сыр" в

Таблицы III и IV. Полный набор экспериментальных результатов можно

на "http://www.cs.toronto.edu/ leehyun / whits ". Кроме того, в связи с

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

со всеми 6 поисковых будет сокращенно

+ +

версия WHITS без Google будет сокращенно

W г и, наконец, версия WHITS без Inktomi

будет сокращенно W

я. Подобные сокращения будут

используется для FWHITS. Так как трудно сформулировать поисковый

Page 5

ТАБЛИЦА III

WHITS / FWHITS VS Google (QUERY: Шекспир)

W + +

F + +

p24

p4 (**)

p19

p4 (**)

p13

p11

p25

p10 (*)

p12

p10 (*)

p4 (**)

p11

p12

p26

p12

p11

p14

p13

p14

p20

p11

p27

p14

p13

p22

p13

p15

p14

p20

p16

p13

p22

p28 (***)

p17

p23 (***)

p15

p21 (**)

p18

p16

p23 (***)

p10 (*)

p19

p21 (**)

p17

p16

p20

p19

p18

p17

p29 (***)

предшествующий

0,9

0,85

0,75

индекс

URL

индекс

URL

http://www.shakespeare.com

http://www.shakespeare.org.uk

http://www.rdg.ac.uk/globe

p4 (**)

http://www.rsc.org.uk

http://www.folger.edu

http://www.shakespeare-oxford.com

http://www.orshakes.org

http://www.shakespearemag.com

http://www.bardweb.net

p10 (*)

http://www.shakespeare.org

p11

http://www.emory.edu/ENGLISH/classes/ ...

p12

http://www.allshakespeare.com

p13

http://www.shakespeare-online.com

p14

http://www.theplays.org

p15

http://www.jetlink.net/ massij / трясет

p16

http://www.bartleby.com/70

p17

http://www.shakespeares-globe.org

p18

http://www.folger.edu/welcome.htm

p19

http://shakespeare.palomar.edu

p20

http://the-tech.mit.edu/Shakespeare/works.html

p21 (**)

http://www.shakespearedc.org

p22

http://www.ipl.org/reading/shakespeare/shakespeare.htm

p23 (***)

http://www.shakespeare-ef.com

p24

http://the-tech.mit.edu/Shakespeare

p25

http://www.gh.cs.usyd.edu.au/ Мэтти / Шекспир

p26

http://www.ipl.org/div/shakespeare/shakespeare.h

p27

http://web.uvic.ca/shakespeare

p28 (***)

http://www.shakespeare-fishing.com

p29 (***)

http://www.shakespeare-ce.com

ТАБЛИЦА IV

WHITS / FWHITS VS Google (QUERY: сыр)

W + +

F + +

p6 (**)

p8 (**)

p6 (**)

p25 (****)

p13

p8 (**)

p10

p8 (**)

p10

p11

p22

p26

p12

p15

p22

p11

p15

p13

p12

p14

p12

p14

p12

p20

p27

p15

p13

p15

p28 (**)

p16

p18

p20

p21

p17

p20

p23

p12

p29

p18

p16

p15

p23

p16

p19 (**)

p17

p18

p30 (**)

p20

p21

p24

p13

p18

предшествующий

0,85

0,9

0,75

индекс

URL

индекс

URL

http://www.ilovecheese.com

p30 (**)

http://www.saycheese.com

http://www.cheese.com

http://www.cheesesociety.org

http://www.wgx.com/cheesenet

http://www.teddingtoncheese.co.uk

p6 (**)

http://www.stringcheeseincident.com

http://www.cheesereporter.com

p8 (**)

http://www.chuckecheese.com

http://www.cabotcheese.com

p10

http://www.stiltoncheese.com

p11

http://www.cheesemaking.com

p12

http://www.fromages.com

p13

http://www.cheeseracing.org

p14

http://www.hilmarcheese.com

p15

http://www.franceway.com/cheese/intro.htm

p16

http://www.astradyne.co.uk/cheese

p17

http://www.idealcheese.com

p18

http://www.tillamookcheese.com

p19 (**)

http://www.cheesewars.com

p20

http://www.vtcheese.com

p21

http://www.specialcheese.com

p22

http://www.sargento.com

p23

http://www.camembert-france.com

p24

http://www.welshcheese.co.uk

p25 (****)

http://www.steakandcheese.com

p26

http://www.aurora.dti.ne.jp/ чи

p27

http://www.friendsofcheese.com

p28 (**)

http://www.cheesestate.com

p29

http://cheesenet.wgx.com

Таблица V

Сравнение метапоиска алгоритмов (QUERY: Шекспир)

W + +

F + +

p20

p19

p4 (**)

p13

p4 (**)

p22 (***)

p26

p4 (**)

p11

p27

p10 (**)

p28 (**)

p11

p14

p12

p10 (**)

p29

p10 (**)

p11

p15

p12

p10 (**)

p12

p23

p11

p12

p14

p13

p14

p21 (**)

p20

p17

p11

p17

p14

p13

p30

p23

p19

p13

p19

p15

p24

p31

p14

p13

p20

p13

p16

p25 (***)

p32

p13

p26

p23

p14

p17

р33 (**)

p25 (**)

p14

p15

p26

p18

p13

p16

p29

p25 (**)

p15

p19

p21 (**)

p12

p34 (**)

p17

p18

p16

p18

p20

p19

p16

p35

p18

p15

p17

p36

предшествующий

0,9

0,85

0,75

0,85

0,9

0,85

0,9

индекс

URL

индекс

URL

http://www.shakespeare.com

http://www.shakespeare.org.uk

http://www.rdg.ac.uk/globe

p4 (**)

http://www.rsc.org.uk

http://www.folger.edu

http://www.shakespeare-oxford.com

http://www.orshakes.org

http://www.shakespearemag.com

http://www.bardweb.net

p10 (**)

http://www.shakespeare.org

p11

http://www.emory.edu/ENGLISH/classes/ ...

p12

http://www.allshakespeare.com

p13

http://www.shakespeare-online.com

p14

http://www.theplays.org

p15

http://www.jetlink.net/ massij / трясет

p16

http://www.bartleby.com/70

p17

http://www.shakespeares-globe.org

p18

http://www.folger.edu/welcome.htm

p19

http://shakespeare.palomar.edu

p20

http://the-tech.mit.edu/Shakespeare/wor

p21 (**)

http://www.shakespearedc.org

p22 (***)

http://www.shakespeare-fishing.com

p23

http://www.ipl.org/reading/shakespeare/ ...

p24

http://shakespeares-globe.org

p25 (***)

http://www.shakespeare-ef.com

p26

http://the-tech.mit.edu/Shakespeare

p27

http://www.williamshakespearesworld.co.uk/ ...

p28 (**)

http://www.bananatv.com

p29

http://absoluteshakespeare.com

p30

http://www.shakespearepapers.com/?so

p31

http://www.chemicool.com/Shakespeare ...

p32

http://daphne.palomar.edu/shakespe

р33 (**)

http://search.ebay.com/search/ ...

p34 (**)

http://www.historyshirt.com/shirt/cgi/ ...

p35

http://web.uvic.ca/shakespeare

p36

http://www.shakespeare-monologues.org

качество в официальном порядке, особенно в контексте веб-

поиск, каждый список был тщательно изучить, чтобы выбрать те,

страниц, которые не имеют отношения к запросу. Страницы, которые кажутся

, что не имеет отношения отмечены (*), то, где число

(*) С указывает на степень их неуместность. На запрос

«Шекспир», Google возвращает 5 страниц, которые не относятся

к предмету, включая "http://www.shakespeare-fishing.com"

, которая является странице компании, которая продает рыболовные снасти

и "http://www.shakespeare-ce.com", который является страницы

компания, которая продает композиционных материалов и электроники. Хотя

производительность W

г и F г не исключительно хорошо

поскольку "http://www.shakespeare-ef.com", который является дубликатом

из "http://www.shakespeare-ce.com" возвращается этих аль-

gorithms, качество страниц возвращается W

+ + , F + + , W г

и F г относительно приемлемым, так как только в их страницах

Списки, которые могут рассматриваться как "плохие результаты" являются домашние страницы

классический театр драмы и компаний, которые также демонстрируют

произведения Шекспира. На запрос "сыр", мы утверждаем,

что производительность W + + , F + + , W и г F г лучше

чем Google, так как их точность выше, и они не

спам как Google является «http://www.steakandcheese.com".

Чтобы получить более полное представление о производительности WHITS

Страница 6

ТАБЛИЦА VI

Сравнение метапоиска алгоритмов (QUERY: классическая гитара)

W + +

F + +

p13

p10

p20

p12

p11

p10

p22

p30 (**)

p14

p10

p7 (*)

p11

p31

p11

p7 (*)

p13

p11

p14

p20

p19

p10

p23

p32

p7 (*)

p10

p7 (*)

p15

p11

p24

p33

p10

p7 (*)

p12

p7 (*)

p34 (**)

p11

p7 (*)

p13

p35

p12

p15

p14

p43

p14

p36

p14

p12

p42

p15

p16

p25 (**)

p37

p15

p19

p15

p16

p15

p26 (*)

р38 (**)

p24

p42

p16

p12

p17

p18

p27

p18

p22

p24

p18

p19

p28

p39

p19

p13

p18

p19

p21

p14

p16

p41

p43

p37

P44 (*)

p20

p17

p29

p40

p16

p19

p22

предшествующий

0,95

0,85

0,95

0,9

индекс

URL

индекс

URL

http://www.classic-guitar.com

http://www.staffordguitar.com

http://fly.hiwaay.net/ marklong / класс

http://www.guitarist.com/cg/cg.htm

http://www.info-internet.net/ ffaucher

http://www.bcgs.org

p7 (*)

http://www.guitarfoundation.org

http://www.widomaker.com/tcgs

http://www.guitarreview.com

p10

http://www.ele.uri.edu/faculty/sun/CGCL.htm

p11

http://www.ccgs.org

p12

http://www.guitar.or.jp/index-e.html

p13

http://www.ashleymark.co.uk/ ...

p14

http://www.classicalguitarstudio.com

p15

http://www.noad.com

p16

http://www.newmillguitar.com

p17

http://www.eythorsson.com

p18

http://www.classicalguitar.net

p19

http://www.classicalguitarstore.com

p20

http://home.att.net/ jorgeguillen

p21

http://www.guitarandlute.com

p22

http://www.info-internet.net/ ffaucher / ffauc

p23

http://alt.venus.co.uk/weed/music/classtab

p24

http://home.wxs.nl/ piete117

p25 (**)

http://www.guitaralive.com

P26 = P44 (*)

http://www.classicalguitar.com

p27

http://www.classicalguitarbuilder.com

p28

http://www.ga-usa.com/cglists

p29

http://www.mindspring.com/ rd2ruin/music.html

p30 (**)

http://www.musicbasics.com/guitars

p31

http://searchpdf.adobe.com/proxies/2/29/99/0.html

p32

http://home.att.net/ nwguitar

p33

http://www.ashleymark.co.uk/classicalguitar

p34 (**)

http://www.rnrgc.com

p35

http://www.classicguitar.com

p36

http://www.wwbw.com/ ...

p37

http://www.guitarsalon.com

р38 (**)

http://www.instrumentexchange.com/searc

p39

http://www.spanishguitars.co.uk

p40

http://www.handpickedguitars.com

p41

http://www.guitarsite.com/bands4.htm

p42

http://www.guitarist.com

p43

http://www.phillyguitar.org

P44 = P26 (*)

http://www.lionaboyd.com

ТАБЛИЦА VII

Сравнение метапоиска алгоритмов (QUERY: BLUES)

W + +

F + +

p7 (**)

p11 (***)

p26 (**)

p13

p23

p13

p10

p7 (**)

p27

p7 (**)

p15

p7 (**)

p28 (**)

p15

p7 (**)

p39

p7 (**)

p10

p7 (**)

p10

p29

p21

p16

p7 (**)

p11 (***)

p12

p21

p39

p21

p12

p14 (**)

p22

p14 (**)

p13

p22

p30 (**)

p12

p10

p22

p14 (**)

p16

p17

p31

p11 (***)

p14 (**)

p15

p10

p15

p12

p32

p16

p12

p16

p11 (***)

p13

р33 (**)

p13

p11 (***)

p14 (**)

p17

p18

p34 (**)

p14 (**)

p17

p13

p16

p18

p19

p23

p35 (**)

p15

p40

p11 (***)

p40

p19

p18

p24

p36 (**)

p38

p41

p43

p41

p20

p25 (**)

p37 (**)

p17

p42

p17

p11 (***)

предшествующий

0,85

0,8

0,55

0,85

индекс

URL

индекс

URL

http://www.hob.com

http://www.bluesworld.com

http://www.bluesrevue.com

http://www.island.net/ блюз

http://www.bluesaccess.com

http://www.blues.org

p7 (**)

http://www.stlouisblues.com

http://www.bluestraveler.com

http://www.thebluehighway.com

p10

http://www.sfblues.com

p11 (***)

http://www.bluesnews.com

p12

http://www.electricblues.com

p13

http://www.mnblues.com

p14 (**)

http://www.moodyblues.co.uk

p15

http://www.torontobluessociety.com

p16

http://www.realblues.com

p17

http://www.bluesandsoul.co.uk

p18

http://www.deltabluesmuseum.org

p19

http://www.dcblues.org

p20

http://www.fred.net/turtle/blues.shtml

p21

http://blueslyrics.tripod.com

p22

http://www.bluesaccess.com/ba home.htm

p23

http://www.blueflamecafe.com

p24

http://www.sunday-blues.com

p25 (**)

http://sportsillustrated.cnn.com/ ...

p26 (**)

http://www.espooblues.fi

p27

http://www.he.net/ блюз

p28 (**)

http://www.amazon.com/exec/obidos/tg/bro

p29

http://dmoz.org/Arts/Music/Styles/Blues

p30 (**)

http://www.showmetickets.com/over/b

p31

http://bluesaccess.com/ba links.html

p32

http://Bluesspell.iuma.com

р33 (**)

http://search.ebay.com/search/ ...

p34 (**)

http://www.izzychait.com

p35 (**)

http://www.umka.com.ua/eng/gg01.shtml

p36 (**)

http://www.authenticjersey.com/NHL

p37 (**)

http://sportsillustrated.cnn.com/hockey/ ...

p38

http://www.mvbs.org

p39

http://www.bigroadblues.com

p40

http://www.bluesfestivals.com

p41

http://www.cascadeblues.org

p42

http://www.newsblues.com

p43

http://www.bluesweb.org

ТАБЛИЦА VIII

Сравнение метапоиска алгоритмов (QUERY: настольный теннис)

W + +

F + +

p25

p26

p27

p28 (*)

p12

p21

p14

p16

p29

p11

p30

p12

p10

p11

p10

p11

p10

p31

p11

p14

p11

p16

p12

p13

p18

p32 (*)

p12

p15

p13

p15

p13

p12

p14

p33

p13

p10

p12

p14

p16

p17

p16

p18

p15

p22

p34

p14

p11

p14

p11

p16

p14

p20

p35 (*)

p15

p18

p37

p10

p17

p18

p23

p13

p19

p13

p15

p13

p18

p17

p37

p20

p18

p38

p19

p24

p17

p38

p17

p39

p20

p10

p36

p18

p39

p20

предшествующий

0,85

индекс

URL

индекс

URL

http://www.ittf.com

http://www.usatt.org

http://www.tabletennis.gr

http://tabletennis.about.com

http://www.etta.co.uk

http://www.ettu.org

http://www.megaspin.net

http://www.tabletennis.org.nz

http://www.ping-pong.com

p10

http://www.tabletennis.se

p11

http://www.ctta.ca

p12

http://www.worldtabletennis.com

p13

http://www.hal-pc.org/~~V canupnet / ttlinks.html

p14

http://www.hardbat.com

p15

http://www.nctta.org

p16

http://www.robbinstabletennis.com

p17

http://www.tabletennis1.com

p18

http://www.butterflyonline.com

p19

http://www.usatt.org/index.shtml

p20

http://www.btinternet.com/ ttaw

p21

http://www.sportsladders.com/tabletennis

p22

http://www.wakkanet.fi/ jkumpuvu

p23

http://homepage.eircom.net/ ojk / tti.html

p24

http://www.patiostore.com/tennis.html

p25

http://www.hedley1945.freeserve.co.uk

p26

http://qxjanc.freeyellow.com/Kiss2ColorRuleGoo

p27

http://www.credit-land.com/tabletennis

p28 (*)

http://www.salesale.net

p29

http://www.totaltabletennis.com/customer

p30

http://encarta.msn.com/encnet/ ...

p31

http://robbinstabletennis.com

p32 (*)

http://www.sears.com/sr/search/category/browseca

p33

http://tabletennis.about.com/mbody.htm

p34

http://www.cornerstonebilliards.com/tabletennis

p35 (*)

http://store.yahoo.com/poolgiant/index.html

p36

http://www.buychoice.com/vendor.cfm/770, Bu

p37

http://www.ttireland.com

p38

http://www.ottf.org.au

p39

http://www.netspace.net.au/ ttenis

и FWHITS, мы сравнили результаты, полученные нашим алгоритмом

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

изобилие (PR) и Vivisimo (VI), который, как известно, производят

хорошие результаты поиска

. Во-первых, мы рассчитали сходство между

20 лучших страниц возвращается метапоиска двигателей и наши

алгоритмы с помощью простых расстояние пересечения и обобщенные

Кендалл-тау расстояния [2]. Сравнение метапоиска двигателей

и наши алгоритмы с простыми расстояние пересечения приведены в

5http :/ / WWW. searchenginewatch.com

Таблица IX в то время как по сравнению с Kendall-тау расстояние дается

в таблице X. Наше метапоиска алгоритмов получены результаты которых

больше похожи на те Vivisimo, чем изобилие.

Один удивительный факт в том, что списки производства WHITS

и FWHITS равнонепротиворечивы при различных условиях

условия (без Google или без Inktomi); разных версий

из WHITS и FWHITS очень похожи, где их сходство

в диапазоне от 0,7854 до 0,9596 при пересечении расстояние

используются и от 0,7460 до 0,9159, когда Кендалл-тау расстояние

используется. Более тщательного изучения со списками производимые нашей

Страница 7

ТАБЛИЦА IX

Подобия (пересечение) TOP 20 страниц

В.В.

+ +

F + +

0,4129

0,3854

0,3725

0,3709

0,3790

0,3661

0,3693

В.В.

0,4129

0,6612

0,6306

0,6016

0,6451

0,6193

0,6032

W + +

0,3854

0,6612

0,8709

0,8177

0,9596

0,8661

0,8258

0,3725

0,6306

0,8709

0,7854

0,8661

0,9419

0,7887

0,3709

0,6016

0,8177

0,7854

0,8258

0,7887

0,9370

F + +

0,3790

0,6451

0,9596

0,8661

0,8258

0,8693

0,8338

0,3661

0,6193

0,8661

0,9419

0,7887

0,8693

0,8016

0,3693

0,6032

0,8258

0,7887

0,9370

0,8338

0,8016

ТАБЛИЦА X

Подобия (тау Кендалла) из 20 СТРАНИЦЫ

В.В.

W + +

F + +

0,4317

0,4169

0,4074

0,4114

0,4091

0,4022

0,4041

В.В.

0,4317

0,6431

0,6187

0,5993

0,6230

0,6024

0,5877

W + +

0,4169

0,6431

0,8528

0,8112

0,9189

0,8228

0,7909

0,4074

0,6187

0,8528

0,7627

0,8316

0,9159

0,7460

0,4114

0,5993

0,8112

0,7627

0,7981

0,75

0,8979

F + +

0,4091

0,6230

0,9189

0,8316

0,7981

0,8443

0,8138

0,4022

0,6024

0,8228

0,9159

0,7500

0,8443

0,7558

0,4041

0,5877

0,7909

0,7460

0,8979

0,8138

0,7558

алгоритмов показало, что производительность нашего метапоиска

Алгоритмы, по крайней мере так хорошо, как Vivisimo и изобилие или

Иногда даже лучше, чем Vivisimo и изобилие с

Единственное исключение из запроса "скалолазание", так как полностью ИК-

соответствующей странице в разделе «http://www.rocknroad.com" (Rhino

Постановка и события Solutions) была возвращена, как лучше всего

наши метапоиска алгоритмов. По непонятным причинам, это

абсолютно никакого отношения страницы высоко оценены большинство

поисковые системы (1-й по HotBot, 3-й по Google, 6-й по Teoma,

Тридцать пятой по AltaVista, 15-ю по AllTheWeb). Таким образом, наши метапоиска

Алгоритмы Оцените эту страницу как самый лучший. Этот пример показывает,

, что с нашей взвешенной подвержены в основном полагается на мнение

поисковые системы, если большинство поисковых систем высоко смещены

определенную страницу, то наш алгоритм как правило, терпят неудачу.

Для краткости мы снова только представить наши

результаты по запросам "Шекспир", "классическая гитара", "блюз"

и "настольный теннис" в таблице V, VI, VII и VIII. На

Запрос «Шекспир», выступление наших алгоритмов

и изобилие приемлемо при Vivisimo не возвращается

хороший власти на тему, поскольку она получает страниц, как

"Http://www.shakespeare-ef.com" (Шекспир и композитов

электроника) и «http://www.shakespeare-fishing.com" (стр.

компании, которая продает рыболовные снасти). На запрос

"Классическая гитара", большинство наших алгоритмов метапоиска за

сформировать лучше, чем Vivisimo и изобилие получение только одного

не имеет значения страницы, а Vivisimo и изобилие получить 3 страницы

, которые кажутся слабыми власти на тему «классическая

гитара ". На запрос "блюз", все поисковые системы и алгоритмов,

ритмы показывают низкие показатели, так как почти все поисковые системы

смещены "http://www.bluesnews.com", который представляет собой страницу

посвященные обзоры игр и различных страниц, связанных с

НХЛ команды Сент-Луис Блюз

. Тем не менее, наши алгоритмы

, кажется, менее предвзято, чем Vivisimo и гораздо лучше, чем

изобилии. Vivisimo занимает "http://www.stlouisblues.com" и

"Http:/www.bluesnews.com", как 3 и 4 ее вершине

6We предполагаем здесь, что запрос "блюз" исключительно относится к

музыки "блюз", а не в НХЛ блюз или любой другой тип "блюз"

20 страниц в то время как изобилие сильно предвзятое возвращение некоторых

не имеет значения страниц, включая страницы, связанные с хоккейной командой

Сент-Луис Блюз. На запрос "настольный теннис", но все изобилие

выполнять хорошо. Profusion не будет работать на эту тему с 3 страниц его

списка страницах компаний, занимающихся продаем оборудование

и аксессуары для внутренней спорта.

V. ЗАКЛЮЧЕНИЕ

В этой работе мы представили алгоритм, основанный на совместном

Цитата модели поисковых систем и страницы подойти к

слияние проблемы. Наша работа открывает возможность применять-

ING другую ссылку анализ алгоритмов слияния с

взвешенная версия любой алгоритм анализа ссылок на веб-страницах

может применяться для совместного цитата граф модели. Так как наша

Алгоритм может быть использован для оценки качества поиска

Двигатели на систематической основе, мы в настоящее время изучает

способы переработки нашей методологии ранжирования поисковых систем.

VI. ПОДТВЕРЖДЕНИЕ

Я хотел бы поблагодарить профессора Аллана Бородина за неоценимую

Комментарии и отзывы на эту работу.

Ссылки

[1] С. Дворк, Р. Кумар, М. и Д. Наор Sivikumar "Ранг агрегации

методы в Интернете ", Proc. 10-я Международная конференция WWW, май

2001 год.

[2] Р. Феджин, Р. Кумар, Д. Sivikumar, "Сравнение списков топ К", Proc.

из ACM-СИАМ симпозиум по дискретных алгоритмов, 2003.

[3] В. Мэн, К. Ю. и К. Л. Лиу, "Создание эффективной и действенной

Метапоиска двигателей ", опросы ACM Computing, 34 (1), стр. 48-89 марта

2002 год.

[4] Дж. М. Аслам и Монтекки., "Модели Мета", Proc. ACM

SIGIR '01, стр. 276-284, 2001.

[5] И. Ли, "Анализ нескольких сочетание доказательств", Proc. ACM

SIGIR 97, стр. 267-275, 1997

[6] BU Oztekin, Г. Karypis и В. Кумар, "Соглашение экспертов и

Содержимое основе Reranking в метапоиска среды с использованием Mearf "

Proc. Одиннадцатой Международной конференции WWW 2002.

[7] А. Фокс и JA Шоу, "Комбинация нескольких запросов",

Второй текст поиска конференция (TREC-2), 1994 год.

[8] Дж. Клейнберг. "Авторитетные источники в гиперссылками окружающей среды",

Proc. из ACM-СИАМ симпозиум по дискретных алгоритмов, 1998.

[9] Р. Lempel и Морана. "Стохастический подход к ссылке структуры

анализ (сальса) и ТКС эффект ". Proc. 9-й Международной

World Wide Web конференции, май 2000 года.

[10], А. Бородина, Г. О. Робертс, С. Розенталя и П. Tsaparas. "В поисках

власти и концентраторы с ссылкой структур на всемирной паутине ", Proc.

10-й Международной конференции WWW, стр. 415-429, май 2001 года.

[11] С. Gauch, Г. Ван, М. Гомес, "Profusion: Intelligent Fusion от

Несколько, распределенные поисковые ", журнал универсального компьютера

Наук, 2 (9) :637-649, 1996.

[12] А. Д. Хау и Dreilinger "SavvySearch: мета-поисковую систему, которая

Учится которые поисковые системы с запросом ", А. И. Magazine, 18 (2), 1997.

[13] Моника Henzinger, Раджив Мотвани, и Крейг Silverstein, «Проблемы

в поисковые машины ". SIGIR Форум 2002

[14] Даниэль Dreilinger и Адель Э. Хоу, "Опыт выбора

поисковые системы использования метапоиска ". ACM Сделки по информации

Системы, 15 (3) :195-222, 1997.

[15] Е. А. Сельберга и Этциони, "Multi-службы поиска и сравнения по

MetaCrawler ", Proc. 4-й Международной World-Wide Web

Конференция, Дармштадт, Германия, декабрь 1995 года.

[16], К. и М. Бхарат Henzinger "Совершенствование алгоритмов Тема дистилляции-

Тион в гиперссылки окружающей среды ", Proc. Двадцать первого ACM SIGIR конференции

1998 год.