Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Поиск в социальных сетях: тенденции и алгоритмы Илья Сегалович (Яндекс)
Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Почему социальная сеть Популярность поиска: обратная сторона Жизнь документов и сайтов: компании и люди, переезды и повторы «Популярность» и посещаемость Ошибки, форматы, «грязь», скрипты Почему анализ текста беспомощен
Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Цитируемость Индекс цитирования (backlinks) Статический ранг: PageRank Локальный ранг: Hits, SALSA, локальный PageRank Ссылочное ранжирование и anchor-text propagation
Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Непотизм – вызов XXI века Внутрисайтовость (в т.ч. IP?) Выявление линкфармов, каталогов само ввода, гестбуков, форумов Тематическая близость? Использование DOM структуры HTML? Что делать с
Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Природа дубликатов Повтор текста – фундаментальная особенность социальной сети Технические причины (в т.ч. «переодетые зеркала») Копирование с редактированием Скрипты
Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Почти-дубликаты Шинглы (требуют кластеризации) «Супершингл» (Яндекс.Почта) Локальные лексические сигнатуры Глобальные лексические сигнатуры (Яндекс)
Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Веб-Каталог: Фасеты vs. Глубина Сколько нужно категорий? Сложная навигация Повтор структур в листьях Темы Регионы (Россия, Москва, …) Жанр (Худ Лит, Науч Тех,...) Доверие к источнику (официальный, пресса, частный, анонимный) … Многомерный каталог
Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Regional Reliability Addressee Domain Topics
Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Кластеризация «каталогом» Визуальная структура результатов Сопровождать документ «темой» Ограничение поиска «темой» Вес группы:
Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Полуавтоматический процесс Аннотировать вершины – не страницы Вес по цитируемости Вес по «размеру» Структура сайта Вершина Тема Цитиру- емость Размер «Вес»
Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Тематическая классификация Лучшие 10,000 слов по TF*IDF 45,000-размерное пространство Наследование признаков 8-10 часов для 30,000,000 документов Встроена в «робота»
Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Стилистичесикй авто классификатор Социальная природа жанра Относительная простота классификации Признаки: морфология (части речи, глагольные формы), лексика (слова из заданных списков), синтаксис (цепочки родительных падежей, '{можно|нужно} + инфинитив), формальные (длина слова, предложения) Составление минимального набора параметров Дискриминантный анализ
Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Морфология Несловарный стемминг. Snowball (80-120) Словарная нормализация: PC-Kimmo, RXRCE (30-50) Словарь = «супер правило». Алгоритм БЫКА (40) (Сегалович, 1996)
Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Поиск по «кворуму» Способ «фильтрации» при поиске Длинные запросы = «нечеткие цитаты» Близкий vs. широкий контекст Многоместный AND с разным контекстом
Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Синтаксический анализ для выявления скрытого контекстного ограничения ATN-грамматика адаптированная для зависимостей Только именные группы Примыкание, притяжение, перечисление
Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Трансформации запроса [что такое сегнетова соль] [сегнетова соль /+1 !%это] [я тебя ненавижу - но ко мне ты все ближе] [+!я +!тебя ненавижу - +!но +!ко +!мне +!ты +!все ближе] [что такое кванза] [кванза /+1 !%это /(-2 4) %означает /(-2 4) %аббревиатура /(-2 4) %расшифровывается"]
Семинар Москоской секции ACM SIGMOD 26 декабря 2002 P2P: Распределенное индексирование Точность предсказания <10% Обмен списками файлов, не индексом Простой текстовый формат протокола Открытая документация V 2 F H U /index.html U /about.html T C d41d8cd ecf8427e V 2 H U /index.html D /about.html?qqq T C d41d8cd ecf8427e Пример реального протокола: Платформы: FreeBSD, Win32, SUN, Linux, HP, Lotus Notes
Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Вопросы? Илья Сегалович