автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Методы повышения эффективности определения показателей цитируемости электронных документов в информационно-поисковых системах

На правах рукописи

/'Л

О

СУРИКОВ Анатолий Георгиевич

МЕТОДЫ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ОПРЕДЕЛЕНИЯ ПОКАЗАТЕЛЕЙ ЦИТИРУЕМОСТИ ЭЛЕКТРОННЫХ ДОКУМЕНТОВ В ИНФОРМАЦИОННО-ПОИСКОВЫХ СИСТЕМАХ

Специальность - 05 13 17 Теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

2 2 СЕН 2

Москва 2008

003446500

Работа выполнена в Московском государственном университете приборостроения и информатики на кафедре «Персональные компьютеры и сети»

Научный руководитель кандидат технических наук, доцент

Зеленю Геннадий Вадимович

Официальные оппоненты доктор технических наук, профессор

Солодовников Игорь Владимирович

кандидат технических наук, Телегин Павел Николаевич

Ведущая организация Государственный научно-исследовательский

институт информационных технологий и телекоммуникаций (ГНИИ ИТТ «Информика»)

Защита состоится 18 сентября 2008 г в 1200 часов на заседании диссертационного совета Д 212 147 03 при Московском государственном университете печати (127550 Москва, ул Прянишникова, 2А)

С диссертацией можно ознакомиться в библиотеке Московского государственного университета печати

Автореферат разослан 18 августа 2008 г

Ученый секретарь диссертационного совета Д212 147 03 д т н , профессор /У/1<ууьг^'^ Агеев В Н

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. В связи с высокими темпами роста объемов представленной в цифровом виде информации, а также с популяризацией глобальных компьютерных сетей и ростом числа их пользователей, задача развития средств информационного поиска и информационно-поисковых систем (ИПС) приобретает сегодня особую актуальность

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

Впервые идея расчета показателя цитируемости и учета этого показателя при вычислении значений релевантности (смыслового соответствия) в ИПС была опубликована в работах Брина и Пейджа в 1998 г Разработанный ими алгоритм PageRank реализован в ИПС Google В течение последующих нескольких лет появилось множество модификаций этого алгоритма

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

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

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

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

Состояние проблемы. При исследовании, разработке и развитии методов и алгоритмов расчета показателей цитируемости документов охватывается широкий круг проблем, связных с оценкой эффективности, оптимизацией вычислительной сложности, информационным поиском и др Здесь следует отметить значительный вклад отечественных и зарубежных ученых И С Некрестьянов, И В Сегалович, Э Э Гасанов, В Б Кудрявцев, MB Ульянов, С Ильинский, M Кузьмин, А Мелков, ИЕ Кураленок, S Brin, L Page, U Manber, A Z Broder, К Bharat, MR. Henanger, JM Kleinberg, M S Manasse, S С Glassman, J Davis, H Garcia-Moltna, N Shivakumar

Существующие публикации по тематике ссылочного ранжирования и цитируемости в информационном поиске посвящены учету факторов «тематичности» и «доверительности», а также усовершенствованию классического алгоритма PageRank с точки зрения его вычислительной эффективности и устойчивости к искусственным «накруткам» результирующих показателей Здесь следует отметить работы Е А Трофименко «Оптимизация расчета ссылочной популярности и учета ее при ранжировании результатов поиска», L Page, S Brin «The PageRank citation Ranking Bringing Order to the Web», С Junghoo, R.Sourashis «Impact of search engines on page popularity», J M Kleinberg «Authontative sources in a hyperlmked environment»

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

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

Цель работы. Целью работы является повышение эффективности алгоритмического и программного обеспечения для определения показателей цитируемости документов и учета фактора «неявного» цитирования

Основные задачи исследования. Достижение поставленной цели предполагает решение следующих основных задач

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

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

- разработка метода определения и учета фактора «неявного» цитирования,

- разработка метода определения порождающего документа в группе нечетких копий документов,

- разработка эффективного метода для определения результирующего показателя цитируемости документов,

- экспериментальное исследование предложенного метода для проверки его эффективности

Научная новизна:

1 Предложен эффективный метод поиска неявных цитат в больших массивах документов (с оценкой 0(п))

2 Разработаны критерии и предложен метод оценки документов в группе нечетких копий для определения порождающего документа.

3 Предложен метод вычисления показателя «неявной» цитируемости

4 Предложен метод определения показателей цитируемости, основанный на методе Кляйнберга и учитывающий показатель «неявной» цитируемости

Практическая ценность результатов работы На основе предложенного метода разработано программное обеспечение для определения показателя цитируемости с учетом фактора «неявной» цитируемости Разработанное программное обеспечение может быть использовано в системах информационного поиска, а также в системах рубрикации и в каталогах электронных документов с целью повышения эффективности ранжирования документов в выдаче Также данное программное обеспечение может быть использовано с целью подавления информационно-поискового спама в выдаче ИПС, так как его важной особенностью является высокая устойчивость определяемых показателей цитируемости к попыткам искусственного влияния извне Разработанное программное обеспечение было внедрено в эксплуатацию ОАО «Сервис+» Основные результаты, выносимые на защиту:

• Метод вычисления показателя «неявной» цитируемости

• Метод определения порождающего документа в группе нечетких копий документов

• Усовершенствованный метод определения показателя цитируемости документов

• Алгоритм повышения эффективности вычисления показателя цитируемости с использованием оригинального метода учета фактора «неявного» цитирования

Апробация работы Основные результаты диссертации были представлены на X Международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики и экономики» (Москва, 2007 г) и на семинаре «Задачи системного анализа, управления и обработки информации» (Москва, 2006 г)

Публикации. Основные результаты по теме диссертации опубликованы в 7 работах, из них 1 - в издании, включенном в перечень ВАК Во всех работах, выполненных в соавторстве с научным руководителем, последнему принадлежит постановка задачи и общее руководство

Структура и объем работы Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы, включающего 94 наименования Материал изложен на 104 страницах машинописного текста, включая 5 таблиц и 9 рисунков

СОДЕРЖАНИЕ РАБОТЫ Во введении кратко рассматривается решаемая проблема, обосновывается актуальность рассматриваемой в работе темы Сформулированы цель диссертационного исследования, научная новизна, практическая ценность работы, основные положения, выносимые на защиту

В главе 1 «Методы и алгоритмы учета ссылочного фактора в информационном поиске, их особенности и области применения» обобщены подходы к повышению качества ранжирования документов в информационном поиске посредствам учета ссылочной составляющей релевантности, в частности, показателя цитируемости Подробно рассмотрен базовый алгоритм вычисления показателя цитируемости Ра§еКапк, а также ряд его модификаций Рассмотрены альтернативные методы и алгоритмы определения показателей цитируемости документов Кляйнберга, Као-Лина и др Выявлены основные недостатки существующих методов

Рассмотрены возможные подходы к повышению эффективности определения показателей цитируемости В заключении главы на основе

проведенного анализа сделан вывод о перспективности использования фактора «неявной» цитируемости для повышения эффективности алгоритмического и программного обеспечения определения показателей цитируемое™ в задачах информационного поиска.

В главе 2 «Вычисление фактора неявной цитируемости и эффективный алгоритм поиска нечетких копий документов» сформулированы требования к быстродействию и необходимой памята для применения алгоритма поиска нечетких копий документов Кратко рассмотрены современные алгоритмические подходы, получена сравнительная оценка их временной эффективное™ и требований к памята В результате исследования в качестве базового метода для целей диссертационной работы выбран метод «шинглов» Манбера и Бродера

«Шингл» - контрольная сумма, рассчитанная для М подряд идущих слов документа. Для оптимального выполнения задач, поставленных в работе, метод «шинглов» был модифицирован Так, например, вычисление «шинглов» осуществляется для каждого законченного предложения Р без перекрытия

VDt,k = lJf 3P = tf,P2 Р,} Vj=1,F Р <|Р|<Р ,

mm — III — max >

U(R) = true,

M

shingle(Pl) = QTiPi[j\mod21') mod 2* ,

м

где D„ - к-й документ, N - количество документов в выборке, Р -предложения, выделенные в документе Dt, Ртт и Рпт - минимально и максимально допустимые длины предложения соответственно, F — количество выделенных в соответствии с условием U(pl) = true предложений в документе Dt, М - количество слов в предложении р,, pt[j] - j-e слово предложения pt, h - битовая длина «шингла», U- правило,

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

U{P,) =

true, если 3/ = l,F: P[j]eTSP,P <\Р\<Р

J 7 it. J J ' mm I 11 ma

true, если 3j = \,F : P\ j] e TSP„Pmm < \P,\ < Pm иначе false

где TSP и TSF - множества знаков пунктуации и знаков форматирования соответственно; Р - предложения, выделенные в документе Dt.

Таким образом, каждый документ D характеризуется персональным вектором SD, образующимся из множества «шинглов», рассчитанных от всех его предложений, удовлетворяющих условию U :

V/ = VF : s, = shingle(Р,), где Si - «шингл» i-го предложения документа £>; F - количество предложений в документе D, удовлетворяющих условию U; shingle -функция расчета шингла от предложения.

А*

D

d:

D

Dч

D;

V£>, : {Pt,P,...Pr} V/ = ÏTF:

T[shingle{ P,)] = +i

/

L 7

2 / ■9 /

-7 A4 /

-1

4 /

Рис. 1. Таблица связных списков Т.

Рассчитанный таким образом вектор «шинглов» 8' подвергается процедуре удаления дублирующихся значений и далее используется для адресации в таблице связных списков Т (рис. 1). Таблица Т соотносит рассчитанные значения «шинглов» со связными списками Тп содержащими

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

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

Ul{N,F) = 2t 2 + {z + g) £f„

(=1

где N - количество документов в выборке, F, - количество предложений в г-м документе, h - битовая длина значений «шинглов», z и g -соответственно, битовые длины значений ссылок адресации связных списков и ссылок адресации документов

Также получены оценки вычислительной сложности алгоритма, реализованного на основе разработанного метода для случая, когда размерность «шингла» не превышает аппаратный регистр Ниже приведены оценки для времени обработки документа и времени поиска цитирующих документов соответственно

Tl(F) = F Р„„ (T, + c,)+F сг+съ = 0(F), UF) = J\{F) + F (L„„ ci+c5) + c6=0(F), где F - количество предложений в документе, Pma - максимальный размер предложения (слов), Тл - количество операций, необходимых для вычисления «шингла», Ьтгх - максимальная длина списка цитирующих документов, с,, с7, с\, с4, с5, с6- константы

Далее во второй главе приводится описание метода определения порождающего документа в группе нечетких копий документов Предложенный метод базируется на расчете нескольких комплексных показателей, а именно показателей, основанных на сравнении атрибутов документов V и W, показателей, основанных на учете гиперссылок L, А и

Я, показателей, основанных на сравнении текстов Г и С Ниже приведены формулы для расчета этих показателей

у РТ,-тт(РТпРТ2 РТЧ)

' тах(РТ„РТ2 РТк)-тт(РТ1,РТ1 РТ„)' РТ = Сгеа/юпРа(е1 + СгсаПопТшге1,

Ю^-ттрРТ,,ЮТ, гРТы)_

w,

' max(;DТ;,//)Г2 iPTN)-mm(iPTt,iPT7 iPTw)' iPTt = IndexationDate, + IndexalionTimel,

где N - количество документов в группе, CreationDatei и CreattonTime, -

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

документа Ц, IndexationPate, и Indexation Типе, - целочисленные значения

даты и времени индексации документа Р,

N

IX,

/,-—*-

шах(/„/2 /„)' A = {aï,a2 aN},

N

а,= 1 —

>i

тах(а1,а2 аы)'

где /Г. - количество гиперссылок, ведущих с документа £>у на документ £>„ - наиболее ранняя дата индексации гиперссылок, ведущих с документа Р) на документ £>

я = №Л яг+яс.

л,=

ЯГ = X j7F * 1DF{I,j) - TF * IPF(AFnj%

м

НС, = ¿|CF *ICPF(i, j) -CF* ICPF(AF„j) |,

где Е, -количество слов в составе документа Д, F, - количество предложений в составе документа Д, TF*IDF(i,j) - значение средневзвешенной частотности терма j в документе Д, CF * ICDF(г, j) -значение средневзвешенной частотности цитаты j в документе Д, AF, -анкор-файл документа Д

Т = {*„/, U,

±(TF*IDF(i,j)-TF*IDF^j)) max(/,,<2 tN)

i£TF*IDF(j,t)

TF * IDF^(i) = *---,

C = {c„c2 c4},

t(CF*ICDF(i,j)-CF*ICDFcJj))

C) _;

max(c,,c2 cj

fcF*/CDFQ,i) CF * ICDFaM = *---,

где Et - количество слов в составе документа Д, Ft - количество предложений в документе Д, TF*IDF(i,j) - значение средневзвешенной частотности терма j в документе Д, CF*ICDF(i,j) - значение средневзвешенной частотности цитаты j в документе Д

На основе рассчитанных таким образом показателей вычисляется результирующий показатель R

Г (v, + ^ (h а, k) + K (h с<) К+К+К

где kl - коэффициент важности показателей оценки атрибутов, к2 -коэффициент важности показателей оценки гиперссылок, к3 - коэффициент важности показателей оценки текстов Порождающий документ Д

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

D g = argmaxr;

felJV

Разработанный метод вычисления показателя «неявной» цитируемости состоит из следующих шагов

1 Разбиение документа D на множество его предложений Pni =1 ,F, по признакам знаков препинания, тегов форматирования и контекстных ограничений, определяющих условие U(P) = true

2 Вычисление «шинглов» для предложений P„i=\,F и формирование

§

3 Поиск соответствий по значениям «шинглов» из S в таблице Т и формирование списка нечетких копий документов G для всех предложений Р, документа D

4 Определение документа-первоисточника Dq в группе G

5 Формирование списка цитирующих документов Я из всех групп нечетких копий G

6 Вычисление показателя «неявной» цитируемости для документа D,

В заключении главы на основе проведенного анализа и сравнения современных методов поиска нечетких копий сделан вывод о целесообразности применения модифицированного метода «шинглов» и разработанного на его основе метода вычисления показателя «неявной» цитируемости для повышения эффективности определения показателей цитируемости документов

В главе 3 «Метод повышения эффективности определения показателей цитируемости электронных документов» разрабатываются метод и алгоритм определения результирующего показателя цитируемости В результате проведенного сравнительного анализа за основу был взят способ, предложенный Кляйнбергом в 1998 году, в соответствии с которым

информационное пространство электронных документов представляется в виде ориентированного графа Оа, такого, что вершины ассоциируются с документами, а ребра - с гиперссылками, размещенными в документах.

о

Рис. 2. Граф информационного пространства документов. Для достижения целей, поставленных в работе, метод Кляйнберга

модифицируется следующим образом:

• в состав множества вершин включаются все документы выборки;

• граф Оа является продуктом объединения графа ребра которого ассоциируются с гиперссылками документов выборки друг на друга, и графа (71игп, ребра которого ассоциируются с «неявными» цитатами документов выборки друг из друга.

Каждой вершине р&У графа 0„ приписаны неотрицательные веса:

• вес авторитетности х , вычисляемый итеративно, так что х ;

р&У

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

• вес цитируемости Vр, вычисляемый итеративно, так что V ;

• и вес цитирования \\>р, вычисляемый итеративно, так что м> <— ■

Р<еУ

При этом веса должны удовлетворять условиям нормировки:

ръУ реУ р^У раУ

Для оценки авторитетности документа р используется критерий А :

Ар =(!-£) хр+к Vр, где хр и - величины собственного веса документа р, соответственно, по гиперссылкам и по цитатам, к - безразмерный коэффициент важности фактора «неявной» цитируемое™

Далее в третьей главе получены оценки вычислительной сложности и требований к памяти для алгоритма определения показателя цитируемости с учетом фактора «неявного» цитарования

= + ^ (£ + 4 Ь),

где N - количество документов в выборке, ^тах - максимальное количество слов в предложении, й- размерность значений шинглов (битов), г, g, Ь -битовые длины значений ссылок адресации связных списков, ссылок адресации документов и значений авторитетности и цитируемое™ соответственно, с, и с2 - константы

В главе 4 «Программная реализация метода определения показателя цитируемое™ документов и экспериментальные оценки» приводятся листинги подпрограмм, разработанных для реализации предложенного в работе метода операции обработки документов, вычисления «шинглов», разбиения документа на предложения, определения порождающего документа в группе нечетких копий и вычисления результирующего показателя цитируемое™ документа

Далее в четвертой главе приведены и проанализированы результаты эксперимента по определению показателей качества разработанного метода и реализованного на его основе программного обеспечения Эксперимент проводился на трех выборках корпус «\уеЬ-страницы» (1200 документов), корпус «энциклопедические статьи» (1500 документов), и корпус «научные статьи» (800 документов)

4500 4000 3500 3000 2500 2000 1500 1000 500 О

Цитат найдено Ссылок найдено

-Ошибки при Ь-4

(1=8

1 2 3 4 Ь 6 7 8 9 10 11 12 13 14 16 16 слов в цитате/ссылке

Рис. 3. Показатели по выборке «у/еЬ-страницы».

8000 тооо 6000 5000 4000 3000 2000 1000 0

1 2 3 4 5 6 ? 8 В 10 11 12 13 14 16 16 слов в цитате/ссылке

Цитат найдено ■Ссыпок найдено при !1=4 Ошибки при Ь=Э

Рис. 4. Показатели по выборке «энциклопедические статьи».

слов в цитате/ссылке

Рис. 5. Показатели по выборке «научные статьи». В качестве численной оценки эффективности введена величина О:

1 аг а2 -а, !=<! 1

где С, - множество всех найденных цитат длиной г; С/, - множество всех найденных гиперссылок длиной /; с!1 и - минимальная и максимальная длина цитаты для оцениваемого интервала.

Для корпуса «\уеЬ-страницы» О (4,16) = 336,85. Для корпуса «энциклопедические статьи» (4,16) =-790,11. Для корпуса «научные статьи» О, (4,16) = 198,23.

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

17

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

В диссертационной работе получены следующие основные результаты

- предложен метод вычисления показателя «неявной» цитируемости,

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

- предложен метод поиска неявных цитат в больших массивах документов с оценкой 0(п),

- разработан алгоритм вычисления показателя цитируемости документов, учитывающий фактор «неявного» цитирования,

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи, опубликованные в ведущих рецензируемых научных журналах, определенных ВАК

1 Суриков, А. Г. Численное выражение обобщенной асессорской оценки релевантности в решении задачи информационного поиска / А Г Суриков // Проблемы полиграфии и издательского дела Известия высших учебных заведений -2007 -№2 -С 57-61

Другие публикации

2 Суриков, А. Г. Неявное цитирование как показатель релевантности в информационном поиске / А Г Суриков // Задачи системного анализа, управления и обработки информации (межвузовский сборник научных трудов) -2006 - № 2 - С 112-118

3 Зеленко, Г. В., Суриков, А. Г. О методах выявления нечетких копий документов /Г В Зеленко , А Г Суриков // Межвузовский сборник научных трудов «Программное и информационное обеспечение систем различного назначения на базе персональных ЭВМ» - 2006 - № 9 -С 98-99

4 Зеленко, Г. В., Суриков, А. Г. Ссылочное ранжирование как метод внетекстового информационного поиска / Г В Зеленко, А Г Суриков // Межвузовский сборник научных трудов «Программное и информационное обеспечение систем различного назначения на базе персональных ЭВМ» -2006 -№9 - С 100-103

5 Суриков, А. Г. О несостоятельности прямого итерационного подхода к анализу результатов выдачи информационно-поисковых систем / А Г Суриков // Научные труды юбилейной X международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики и экономики» -2007 - С 167-170

6 Суриков, А. Г. Реализация поиска текстовых шаблонов с помощью конечных автоматов / А Г Суриков // Вестник МГУПИ - 2007 - № 3 -С 58-62

7 Суриков, А. Г. Факторный анализ на больших выборках данных / А Г Суриков // Межвузовский сборник научных трудов «Программное и информационное обеспечение систем различного назначения на базе персональных ЭВМ» -2007 -№10 - С 127-129

ЛР № 020418 от 18 октября 1997 г

Подписано к печати 04 08 2008 г Формат 60x84 1/16 Объем 1,25 п л Тираж 100 экз Заказ №73

Московский Государственный университет приборостроения и информатики

107996, Москва, ул Стромынка, 20

ВВЕДЕНИЕ

ГЛАВА 1 МЕТОДЫ И АЛГОРИТМЫ УЧЕТА

ССЫЛОЧНОГО ФАКТОРА В ИНФОРМАЦИОННОМ ПОИСКЕ, ИХ ОСОБЕННОСТИ И ОБЛАСТИ ПРИМЕНЕНИЯ

1.1 Введение

1.2 Ссылочный фактор как показатель в 13 информационном поиске

1.3 Методы и алгоритмы определения показателей 18 цитируемости электронных документов

1.4 Особенности и области применения 22 показателей цитируемости электронных документов

2.2 Методы поиска нечетких копий электронных 29 документов, их анализ и сравнение

2.3 Метод поиска неявных цитат в больших 46 массивах электронных документов

2.4 Определение порождающего документа в 49 группе нечетких копий электронных документов

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

2.6 Заключение 59

ГЛАВА 3 МЕТОД ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ 61 ОПРЕДЕЛЕНИЯ ПОКАЗАТЕЛЕЙ ЦИТИРУЕМОСТИ ЭЛЕКТРОННЫХ ДОКУМЕНТОВ

3.1 Введение 61

3.2 Методы определения показателей 62 цитируемости электронных документов, метод Кляйнберга

3.3 Фактор «неявной» цитируемости и его 70 применение для определения результирующего показателя цитируемости

3.4 Заключение 72

ГЛАВА 4 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МЕТОДА 74 ОПРЕДЕЛЕНИЯ ПОКАЗАТЕЛЯ ЦИТИРУЕМОСТИ ДОКУМЕНТОВ И ЭКСПЕРИМЕНТАЛЬНЫЕ ОЦЕНКИ

4.1 Введение 74

4.2 Описание алгоритма определения показателя 75 «неявной» цитируемости

4.3 Описание алгоритма определения 82 результирующего показателя цитируемости

4.4 Оценка временной эффективности и 84 требований к памяти

4.5 Экспериментальная оценка эффективности 86 метода определения цитируемости электронных документов

4.6 Заключение 89

ЗАКЛЮЧЕНИЕ 90

БИБЛИОГРАФИЧЕСКИЙ СПИСОК 94 введение

Актуальность темы. В связи с высокими темпами роста объемов представленной в цифровом виде информации [28], а также с популяризацией глобальных компьютерных сетей и ростом числа их пользователей [ЪЩ7 задача развития средств информационного поиска и. информационно-поисковых систем (ИПС) приобретает сегодня особую актуальность.

Одним из последних важнейших достижений в области развития ИПС являются методы определения показателей цитируемости [6J электронных документов (далее - документов). Эти методы позволяют существенно улучшить качество ранжирования в результатах выдачи ИПС по релевантности, являются эффективным способом борьбы с информационно-поисковым текстовым стамом, а также играют важную роль в оптимизации работы ИПС.

Впервые идея расчета показателя цитируемости и учета этого показателя при вычислении значений релевантности (смыслового соответствия) в ИПС была опубликована в работах Крина и Пейджа в 1998 г. Разработанный ими алгоритм PageRank [9,45]. реализован в ИПС Google. В течение последующих нескольких лет появилось множество модификаций того алгоритма [2,15,55]

Существуют также альтернативные методы и алгоритмы вычисления показателей цитируегмоети [35,36, 56,58,61}. В их основе лежит общая идея: расчет численного показателя цитируемости данного документа среди множества других документов выборки [82]. Единственным источником информации о цитируемости для всех разработанных, на сегодня методов являются гиперссылки формализованные ссылки в тексте одного документа, указывающие на другой документ и содержащие адрес его местонахождения).

Однако практика использования разработанных, на основе таких методов алгоритмов выявила ряд их недостатков [18,10]. Во-первых, как было сказано выше, при определении показателей цитируемости учитываются только гиперссылки, а это лишь часть сиг общего числа ссылок и дитат. Зо-вторых, они слабо защищены от попыток искусственной «накрутки» результирующего показателя, и на смену текстовому «спаму» пришел «спам» ссылочный - документы со специально проставленными гиперссылками с авторитетных ресурсов;, не содержащие полезной информации в контексте поискового запроса. И, наконец, в-третьих, все популярные реализации расчета показателей цитируемости документов довольна ресурсоемки.

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

Состояние проблемы. При исследовании, разработав и развитии методов и алгоритмов расчета показателей цитируемости документов охватывается широкий круг проблем, связных с оценкой эффективности, оптимизацией вычислительной сложности, информационным поиском и др. Здесь следует отметить значительный вклад отечественных и зарубежных ученых: И. С. Некрестьянов [78-811, И. В. Сегалович [83-851 Э. Э. Гасанов, В. Б. Кудрявцев [65], М. В. Ульянов [92-93], С. Ильинский, М. Кузьмин, А. Мелков [33], S. Brin [9], L. Page [9,45], U. Manber [42], A. Broder [11], a A. МсВгуаа [44], К. Bharat [Щ, M. R Henzinger [8], J. M, Kleinberg [13,30,31,36], M. S. Manasse [11,23], S. C. Glassman

11,60], H. Garcia-Mofina [3,14,32,52], N. Shivakumar [52J, P. Doreian [19,201, S. Abiteboul [1], В. H. Bagdikian [51, M. Marchiori [43], D. Gibson [13,30].

Существующие публикации гто тематике ссылочного ранжирования и цитируемости в информационном поиске посвящены учету факторов- «тематичности» и «доверительности» [35,36}, а также-усовершенствованию классического алгоритма PageRank с точки зрения его вычислительной эффективности и устойчивости к искусственным «накруткам» результирующих показателей [8,12]. Здесь следует отметить работы Е. А. Трофименко «Оптимизация расчета ссылочной популярности и учета ее при ранжировании результатов поиска» [91]; L. Page, S. Brin «The PageRank citation Ranking: Bringing Order to- the Web» [45]; C.Jtmghoo, R.Sourashis «Impact of search engines on page popularity»- [15]; J.M. Kleinberg «Authoritative sources in a hyperlinked environment» [36]; R. Weiss, B. Velez, M. Sheldon, С Manprempre, P. Szilagyi, A. Duda, D. Gifford «А Hierarchical Network Search Engine that Exploits Content-Link Hypertext Clustering» [56]; E. Spertus «Mining Structural Information on the Web» [54], A. Frieze, R. Kannan, S. Vempala « Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations »- £26}.

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

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

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

Основные задачи исследования. Достижение поставленной цели предполагает решение следующих основных задач:

- анализ существующих методов и алгоритмов определения показателей цитируемости документов;

- определение основных недостатков существующих методов, поиск путей по их устранению;

- разработка метода определения и учета фактора «неявного» цитирования;

- разработка метода определения порождающего документа в группе нечетких копий документов;

- разработка эффективного метода для определения результирующего показателя цитируемости документов;

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

Научная новизна:

1. Предложен эффективный метод поиска неявных цитат в больших массивах документов (с оценкой 0(п)).

2. Разработаны критерии и предложен метод оценки документов в группе нечетких копий для определения порождающего документа.

Предложен метод вычисления показателя «неявной» цитируемости.

4. Предложен метод определения показателей цитируемости, основанный на методе Кляйнберга и учитывающий показатель «неявной» цитируемости.

Практическая ценность результатов работы. На основе предложенного метода разработана программное обеспечение для определения показателя цитируемости с учетом фактора «неявной» цитируемости. Разработанное программное обеспечение может бьггь использовано в системах информационного поиска, а также в системах рубрикации и в каталогах электронных документов с целью повышения эффективности ранжирования документов в выдаче. Также данное программное обеспечение может бьггь использовано с целью подавления информационно-поискового спама в выдаче ИПСГ так как его важной особенностью является высокая устойчивость определяемых показателей цитируемости к попыткам искусственного влияния извне. Разработанное программное обеспечение было внедрено в эксплуатацию ОАО «Сервис-*-».

Основные результаты, выносимые на защиту: Метод вычисления показателя «нежной» цитируемости.

• Метод определения порождающего документа в группе нечетких копий документов-.

• Усовершенствованный метод определения показателя цитируемости документов.

• Алгоритм повышения эффективности вычисления показателя цитируемости. с использованием оригинального метода учета фактора «неявного» цитирования.

Апробацшг работы. Основные результаты диссертации" бвгли представлены на X Международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики и экономики» (Москва, 2007 г.) и на семинаре «Задачи системного анализа, управления и обработки информации» (Москва, 2006 г.).

Публикации. Основные результаты па теме диссертации опубликованы в 7 работах [70,71,86-90], из них 1 - в издании, включенном в перечень ВАК". Во всех работах, выполненных в соавторстве с научным руководителем, последнему принадлежит постановка задачи и общее руководство.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы, включающего 94 наименования. Материал изложен на 104 страницах машинописного текста, включая 5 таблиц и 9 рисунков.

Основные результаты работы

В диссертационной работе получены следующие основные результаты:

- предложен метод вычисления показателя «неявной» цитируемости;

- разработан метод определения порождающего документа в группе нечетких копий;

- предложена оригинальная модификация метода вычисления показателей цитируемости Кляйнберга, учитывающая фактор «неявного» цитирования;

- предложен метод поиска неявных цитат в больших массивах документов с оценкой 0(п);

- разработан алгоритм вычисления показателя цитируемости документов, учитывающий фактор «неявного» цитирования;

- разработан алгоритм, основанный на методе «шинглов» для поиска цитат в больших массивах документов;

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

Перспективы

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

Автор считает своим приятным долгом поблагодарить своего научного руководителя Геннадия Вадимовича Зеленко за помощь и участие.

Автор также выражает признательность Михаилу Васильевичу Ульянову и Алексею Васильевичу Рощину, оказывавшим в ходе работы помощь советами, замечаниями и рекомендациями.

заключение

Краткий обзор проделанной работы

В ходе работы были решены следующие задачи:

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

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

- разработан метод и алгоритм для определения показателя «неявной» цитируемости документов, базирующийся на модифицированном методе «шинглов» Манбера и Бродера; проведено экспериментальное исследование для установления его эффективности;

- разработан метод определения порождающего документа в группе нечетких копий;

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

- разработан метод и алгоритм определения результирующего показателя цитируемости, базирующийся на модифицированном методе Кляйнберга и учитывающий показатель «неявного» цитирования;

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

- проведена экспериментальная оценка эффективности предложенного в работе метода и разработанного на его основе алгоритма определения показателя цитируемости документов с учетом фактора «неявного» цитирования.

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

1. Abiteboul, S., Vianu, V. Queries and Computation on the Web / S. Abiteboul, V. Vianu // Proceedings of the International Conference on Database Theory. 1997.2. . Albert, R., Barabasi, A., Jeong, H. Diameter of the World

2. Wide Web / R. Albert, A. Barabasi, H. Jeong. // Nature. -1999.

3. Bagdikian, В. Н. The Media Monopoly / В. Н. Bagdikian // Beacon 1997.

4. Berners-Lee, Т., Cailliau, R., Luotonen, A., Nielsen, H. F., Secret, A. The World-Wide Web / T. Berners-Lee, R. Cailliau, A. Luotonen, H. F. Nielsen, A. Secret. // Communications of the ACM. -№37.- 1994.

5. Berson, T. A. Differential Cryptanalysis Mod 232 with Applications to MD5 / T. A. Berson / EUROCRYPT. -1992.

6. Bharat,,K., Henzinger, M. Improved algorithms for topic distillation in a hyper-linked environment / K. Bharat, M. Henzinger. // 21st International ACM SIGIR Conference on Research and Development in Information Retrieval. -1998.

7. Brin, S., Page, L. The Anatomy of a Large-Scale Hypertextual Web Search Engine / S. Brin, L. Page // http://www7.scu.edu.au/programme/fullpapers/1921/coml9 21.htm. -1998.

8. Chakrabarti, S., Joshi, M., Tawde, V. Enhanced Topic Distillation using Text, Markup Tags, and Hyperlinks / S. Chakrabarti., M. Joshi, V. Tawde // SIGIR'01, September. 2001.

9. Cho, J., Garcia-Molina, H, Page, L., Crawling, E. Through URL Ordering / J. Cho, H .Garcia-Molina, L. Page. E. Crawling // Seventh International Web Conference (WWW 98). -1998.

10. Cho, J., Sourashis, R. Impact of Search Engines on Page Popularity / J. Cho, R. Sourashis // http://oak.cs.ucla.edu/~cho/papers/cho-bias.pdf . UCLA. -2003.

11. Chowdhury, A., Frieder, O., Grossman, D., McCabe, M. Collection statistics for fast duplicate document detection / A. Chowdhury, O. Frieder, D. Grossman, M. // ACM Transactions on Information Systems (TOIS). №20. -2002.

12. Church, K., Gale, W. Poisson mixtures / K. Church, W. Gale. // Natural Language Engineering . 1995.

13. Del Corso, G. M., Francesco Romani, A. G. Comparison of Krylov subspace methods on the PageRank problem / G.

14. M. Del Corso, A. G. Francesco Romani. // Journal of Computational and Applied Mathematics. №210. - 2007.

15. Doreian, P. Measuring the relative standing of disciplinary journals / P. Doreian // Inf. Proc. And Management — № 24. -1988.

16. Doreian, P. A measure of standing for citation networks within a wider environment / P. Doreian // Inf. Proc. and Management. -№?>Q. -1994.

17. Donath, W. E., Homan, A. J. Lower bounds for the partitioning of graphs / W. E. Donath, A. J. Homan // IBM Journal of Research and Development. —№ 17. — 1973.

18. Egghe, L. Mathematical relations between impact factors and average number of citations / L. Egghe // Inf. Proc. and Management. -№ 24. 1988.

19. Fetterly, D., Manasse, M., Najork, M. A Large-Scale Study of the Evolution of Web Pages / D. Fetterly, M. Manasse, M. Najork // WWW2003. 2003.

20. Fielder, M. Algebraic connectivity of graphs / M. Fielder // Czech. Math. -./№23.-1973.

21. Frakes, W. B., Baeza-Yates, D., C. Information Retrieval: Data Structures and Algorithms / W. B. Frakes, D. C. Baeza-Yates //Prentice-Hall. 1992.

22. Frieze, A., Kannan, R., Vempala, S. Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations / A. Frieze, R. Kannan, S. Vempala, // Proc. 39th IEEE Symp. on Foundations of Computer Science. 1998.

23. Gabrielli, S., Mizzaro, S. Negotiating a Multidimensional Framework for Relevance Space / S. Gabrielli, S. Mizzaro // In Proc. of the MLRA'99. 1999.

24. Gavin, J. Russia Has Fastest Growing Internet Population in Europe / J. Gavin // comScore. 2007.

25. Gibson, D., Kleinberg, J., Raghavan, P. Inferring Web Communities from Link Topology / D. Gibson, J. Kleinberg, P. Raghavan // Proc. 9th ACM Conference on Hypertext and Hypermedia. 1998.

26. Gibson, D., Kleinberg, J., Raghavan, P. Clustering Categorical Data: An Approach Based on Dynamical Systems / D. Gibson, J. Kleinberg, P. Raghavan // Proc. 24th Intl. Conf. on Very Large Databases. 1998.

27. Gravano, L.,Garcia-Molina, H., Tomasic, A. The Effectiveness of GIOSS for the Text-Database Discovery Problem. / L. Gravano, H. Garcia-Molina, A. Tomasic // Proc. of the 1994 ACM SIGMOD International Conference On Management Of Data. 1994.

28. Kaszkiel, M., Zobel, J., Sacks-Davis, R. Efficient Passage Ranking for Document Databases / M. Kaszkiel, J. Zobel, R. Sacks-Davis // TOIS. 1999.

29. Kao.,H. U., Lin, S.H., Ho, J. M., Chen, M. S. Entropy-Based Link Analysis for Mining Web Informative Structures / H. U. Kao, S. H. Lin, J. M. Ho, M. S. Chen // CIKM,02. — 2002.

30. Kleinberg, J., M. Authoritative Sources in a Hyperlinked Environment / J. M. Kleinberg // http://www.cs.cornell.edu/home/kleinber/auth.pdf. 2002.

31. Kolcz, A., Chowdhury, A., Alspector, J. Improved Robustness of Signature-Based Near-Replica Detection via Lexicon Randomization / A. Kolcz, A. Chowdhury, J. Alspector // KDD. 2004.

32. Kolcz, A., Chowdhury, A., Alspector, J. The Impact of Feature Selection on Signature-Driven Spam Detection / A. Kolcz, A. Chowdhury, J. Alspector // The First Conference on Email and Anti-Spam. 2004.

33. Kolcz, A., Chowdhury, A., Alspector, J. Improved Robustness of Signature-Based Near-Replica Detection via Lexicon Randomization / A. Kolcz, A. Chowdhury, J. Alspector // KDD 2004. http://ir.iit.edu/~abdur/publications/470-kolcz.pdf. 2004.

34. Lewis, D. Evaluating and optimizing autonomous text classification systems / D. Lewis // In Proc. of the SIGIR'95. -1995.

35. Lewis D. D., Schapire R. E., Callan J. P., Papka R. Training algorithms for linear text classifiers. In Proc. of the SIGIR'96, pp. 298-306, 1996.

36. Manber, U. Finding similar files in a large file system / U. Manber // USENIX Conference. 1994.

37. Marchiori, M. The Quest for Correct Information on the Web: Hyper Search Engines / M. Marchiori // The Sixth International WWW Conference (WWW 97). 1997.

38. McBryan, O. A. GENVL and WWWW: Tools for Taming the Web / O. A. McBryan // First International Conference on the World Wide Web. 1994.

39. Page, L. The PageRank Citation Ranking: Bringing Order to the Web / L. Page // http://hci.stanford.edu/~page/papers/pagerank.-1998

40. Park, S. T., Pennock, D., Giles C. L., Krovetz, R. Analysis of Lexical Signatures for Finding Lost or Related Documents / S. T. Park, D. Pennock, C. L. Giles, R. Krovetz // SIGIR'02. 2002.

41. Pinkerton, B. Finding What People Want: Experiences with the WebCrawler / B. Pinkerton // The Second International WWW Conference Chicago. 1994.

42. Rijsbergen, C. V. Foundation of evaluation / C. V. Rijsbergen // Journal of Documentation. 1974.

43. Rijsbergen, C. J. Information Retrieval / C. V. Rijsbergen // 2nd ed. Butterworths. 1979.

44. Robertson, S., Walker, S., Jones, S., Hancock-Beaulieu, M., Gatford, M. Okapi at trec-3 / S. Robertson, S. Walker, S. Jones, M. Hancock-Beaulieu, M. Gatford // The Third Text REtrieval Conference (TREC-3). 1995.

45. Shannon, C. E. A mathematical theory of communication / C. E. Shannon. // Bell system technical Journal. — №27. — 1948.

46. Shivakumar, N., Garcia-Molina, H. Finding near-replicas of documents on the web / N. Shivakumar, H. GarciaMolina // Proceedings of Workshop on Web Databases. -1998.

47. Schmidt, C. LocalRank: Google's 2 rankings & you /

48. C. Schmidt // http://clsc.net/research/googles-2-rankings.htm. -1997.

49. Spertus, E. ParaSite: Mining structural information on the Web / E. Spertus // Proc. 6th International World Wide Web Conference. -1997.

50. Tomlin, J., A. A new paradigm for ranking pages on the world wide web. / J. A. Tomlin // In Proceedings of the International World-Wide Web Conference. 2003.

51. Weiss, R., Velez, B., Sheldon, M., Manprempre, C., Szilagyi, P., Duda, A., Gifford, D. HyPursuit: A Hierarchical Network Search Engine that Exploits ContentLink Hypertext Clustering / R. Weiss, B. Velez, M. Sheldon, C. Manprempre, P. Szilagyi, A. Duda,

52. D. Gifford // Proceedings of the 7th ACM Conference on Hypertext. -1996.

53. Wilkinson, J., Zobel, J., Sacks-Davis, R. Similarity Measures for Short Queries / J. Wilkinson, J. Zobel, R. Sacks-Davis // TREC. 1995.

54. Wills, C. E., Mikhailov, M. Towards a better understanding of web resources and server responses for improved caching / C. E. Wills, M. Mikhailov // In Proceedings of the International World-Wide Web Conference. 1999.

55. Witten, I. H., Moffat, A., Bell, Т. C. Managing Gigabytes: Compressing and Indexing Documents and Images / I. H. Witten, A. Moffat, T.C.Bell // New York: Van Nostrand Reinhold. -1994.

56. Wright, M. H., Glassman, S. C. Fortran Subroutines to Solve the Linear Least-Squares Problem and Compute the Complete Orthogonal Factorization / M. H. Wright, S. C. Glassman // Stanford University. 1978.

57. Yang, Y. An evaluation of statistical approaches to text categorization. / Y. Yang // Information Retrieval. 1999.

58. Yang, Y., Pederson, J. Feature selection in statistical learning of text categorization. / Y. Yang, J. Pederson // In Proc. of the ICML'97. 1997.

59. Агеев, M. С., Губин, M. В., Добров, Б. В.,

60. Гасанов. Э. Э., Кудрявцев, В. Б. Теория хранения и поиска информации / Э. Э. Гасанов, В. Б. Кудрявцев // Наука. 2002.

61. Гасфилд, Д. Строки, деревья и последовательности в алгоритмах / Д. Гасфилд. // Невский диалект 2003.

62. Гулин, А., Маслов, М., Сегалович, И. Алгоритм текстового ранжирования Яндекса на РОМИП-2006 // А. Гулин, М. Маслов, И. Сегалович // Труды РОМИП'2006. 2006.

63. Гулин, А., Маслов, М., Сегалович , И. Алгоритм текстового ранжирования Яндекса на РОМИП-2006 /

64. A. Гулин, М. Маслов, И. Сегалович // Труды РОМИП'2006.http://download.Yandex.ru/companv/03 vandex.pdf . — 2006.

65. Добрынин, В. Ю., Клюев, В. В, Некрестьянов, И. С. Оценка тематического подобия текстовых документов /

66. B. Ю. Добрынин, В. В. Клюев, И. С. Некрестьянов // Труды второй всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции». — 2000.

67. Зеленков, Ю. Г, Сегалович, И. В. Сравнительный анализ методов определения нечетких дубликатов для \УеЪ-документов / Ю. Г. Зеленков, И. В. Сегалович // Девятая конференция КСБЬ. 2007.

68. Кристофидес, Н. Теория графов. Алгоритмический подход. / Н. Кристофидес // Мир. 1978.

69. Кнут, Д. Искусство программирования для ЭВМ. / Д. Кнут//Мир.-1976.

70. Кураленок, И. Е., Некрестьянов, И. С. Оценка систем текстового поиска / И. Е. Кураленок, И. С. Некрестьянов // Санкт-Петербургский Государственный Университет. 2004.

71. Лунегов, С. В., Некрестьянов, И. С. Нормализация документов для полнотекстового поиска / С. В. Лунегов, И. С. Некрестьянов // Труды Всероссийской научно-методической конференции «Интернет и современное сообщество»1 (1М8'98). — 1998.

72. Михайлов, Б. М., Ульянов, М. В. Инструментальные средства для исследования эффективности алгоритмов: концепция и основные принципы построения / Б. М. Михайлов, М. В. Ульянов // Информационные технологии. — №1. — 2006.

73. Некрестьянов, И. С., Некрестьянова, М. С. РОМИП'2003: отчет организаторов / И. С. Некрестьянов, М. С Некрестьянова / Труды РОМИП'2003. -2003.

74. Некрестьянов, И. С., Некрестьянова, М. С. РОМИП'2004: отчет организаторов / И. С. Некрестьянов, М. С Некрестьянова / Труды РОМИП'2004.-2004.

75. Некрестьянов, И. С., Некрестьянова, М. С. РОМИП'2005: отчет организаторов / И. С. Некрестьянов, М. С Некрестьянова / Труды РОМИП'2005. -2005.

76. Некрестьянов, И. С., Некрестьянова, М. С. РОМИП'2006: отчет организаторов / И. С. Некрестьянов, М. С Некрестьянова / Труды РОМШТ2006. -2006.

77. Райдингс, К., Вейл, Д., Садовский, А. Растолкованный PageRank / К. Райдингс, Д. Вэйл, А. Садовский // http://digits.ru/articles/promotion/pagerank.html.- 2002.

78. Сегалович, И., Тейблюм, Д., Дилевский, А. Принципы и технические методы работы с незапрашиваемой корреспонденцией / И. Сегалович, Д. Тейблюм, А. Дилевский // http://company.vandex.ru/articles/spamooborona.html . — 2004.

79. Сегалович, И., Маслов, М. Некоторые аспекты полнотекстового поиска и ранжирования в Яндекс / И. Сегалович, М. Маслов // РОМИП-2004. http://romip.ru/romip2004/07 vandex.pdf. 2004.

80. Сегалович, И. В., Зеленков, Ю. Г., Нагорнов, Д. О. Методы сравнительного анализа современных поисковых систем и определения объема Рунета / И. В. Сегалович, Ю. Г. Зеленков, Д. О. Нагорнов // Восьмая конференция ИСБЬ. 2006.

81. Суриков; А. Г. Численное выражение обобщенной асессорской оценки релевантности в решении задачи информационного поиска / А. Г. Суриков // Проблемы полиграфии и издательского дела: Известия высших учебных заведений. №2. - 2007.

82. Суриков, А. Г. Неявное цитирование как показатель релевантности в информационном поиске / А. Г. Суриков // Задачи системного анализа, управления и обработки информации (межвузовский сборник научных трудов). №2. - 2006.

83. Суриков, А. Г. Реализация поиска текстовых шаблонов с помощью конечных автоматов / А. Г. Суриков // Вестник МГУПИ. №3. - 2007.

84. Суриков, А. Г. Факторный анализ на больших выборках данных / А. Г. Суриков // Межвузовский сборник научных трудов «Программное и информационное обеспечение систем различного назначения на базе персональных ЭВМ» . — № 10. — 2007.

85. Трофименко, Е. Оптимизация расчета ссылочной популярности и учета ее при ранжированиирезультатов поиска / Е. Трофименко // http://companv.vandex.ru/grant/2005/06 Тгойтепко 1018 03.pdf. 2005.

86. Ульянов, М. В. Классификация и методы сравнительного анализа вычислительных алгоритмов / М. В. Ульянов // Монография. 2004.

87. Ульянов, М. В., Головешкин, В. А. Метод классификации вычислительных алгоритмов по сложности на основе угловой меры асимптотического роста функций / М. В. Ульянов, В. А. Головешкин // Вычислительные технологии. № 1. - 2006.

88. Харари, Ф., Палмер, Э. Перечисление графов / Ф. Харари, Э. Палмер. / Мир. 1977.