Основы информационного поиска

2024/2025

Учебный год

RUS

Обучение ведется на русском языке

Кто читает:

Департамент больших данных и информационного поиска

Статус:

Курс по выбору

Когда читается:

3-й курс, 1, 2 модуль

Преподаватель

Неганов Алексей Михайлович

Программа дисциплины

Аннотация

Ряд приложений используют так называемый полнотекстовый поиск для поиска по неструктурированным текстовым документам. Это может быть поиск в Интернете, системы поиска по архивным данным (в т. ч. eDiscovery), а также разнообразные базы данных с гибкой схемой данных.В курсе разбираются основные проблемы реализации такого поиска, как поисковые движки устроены изнутри и как они выполняют запросы.

Цель освоения дисциплины

• Уметь применять сжатые битовые вектора для организации обратных индексов, в частности Roaring bitmaps. Владеть техниками “bit-sliced indexing” и “binning” для индексации целочисленных признаков документов, а также признаков – чисел с плавающей точкой с целью поиска документов по диапазону индекса.
• Уметь индексировать документы по дате и строить темпоральные индексы, в частности для индексации снапшотов.
• Иметь начальное представление об использовании сжатых индексов для поиска по произвольной подстроке (на примере FM-index).
• Владеть алгоритмами сортировки результатов по релевантности: tf-idf, vector space.
• Владеть семантическим поиском: latent models, word / sentence / document embeddings. Проклятие размерности, техники понижения размерности. ANN, LSH, randomized k-d tree, vector quantization, k-means tree, HNSW graphs, randomized PCA.
• Уметь тестировать алгоритмы поиска и оценивать релевантность выдачи.

Планируемые результаты обучения

• Знать особенности внешней памяти (HDD, SSD), ведущие к необходимости особых видов индексов. Знать структуры для индексации данных во внешней памяти: B-деревья, LSM-деревья с различными алгоритмами слияния, условия для их применения.
• Знать устройство обратных индексов для булева поиска по данным.
• Знать вариации обратного индекса для фразового поиска: индекс с двойными словами, индекс с позициями
• Знать техники для поиска по префиксу / суффиксу в обратном индексе; знать техники для поиска по паттерну в обратном индексе и техники для исправления опечаток
• Знать особенности индексации различных человеческих языков, в частности восточноазиатских, техники для токенизации текста
• Знать индексы для многомерных данных: R-деревья, k-d деревья

Содержание учебной дисциплины

• Особенности внешней памяти (HDD, SSD), ведущие к необходимости особых видов индексов. Структуры для индексации данных во внешней памяти: B-деревья, LSM-деревья. Схемы слияния компонент для LSM-деревьев. Фильтры Блума.
• Обратные индексы для булева поиска по текстовым документам. Токенизация, стоп-слова, стемминг, лемматизация. Использование n-gram для восточноазиатских языков, словарных корней для немецкого / финского.
• Сжатые битовые вектора, roaring bitmaps.
• Индексация документов по дате.
• Обратные индексы для фразового поиска.
• Использование сжатых индексов для поиска по произвольной подстроке (на примере FM-index).
• Индексы для многомерных данных: R-деревья, k-d деревья. Поиск включения точки в индекс, поиск ближайшего соседа.
• Сортировка результатов поиска по релевантности: tf-idf, vector space. “Inexact top K” ранжирование.
• Семантический поиск: latent models VS word / sentence / document embeddings.
• Проклятие размерности, понижение размерности. ANN, LSH, randomized PCA.
• Продолжение темы: randomized k-d tree, vector quantization, k-means tree, HNSW graphs.
• Тестирование алгоритмов поиска, оценка релевантности выдачи.
• Популярное ПО для полнотекстового и семантического поиска.
• Поиск в Web.

Элементы контроля

• Домашнее задание 1
  Реализовать LSM-дерево со строковыми ключами (levelled / tiered — на выбор). Дисковые компоненты должны поддерживать бинарный или иной логарифмический поиск без полной выгрузки в RAM. Обязательны Блум-фильтры для компонент. Написать бенчмарки для вставки, чтения по ключу, чтения короткого диапазона.
• Домашнее задание 2
  Постройте обратный индекс для набора текстовых документов, используя Roaring bitmaps. A) Построить индекс (хотя бы в памяти), что позволит выдавать документы, для которых верна булева формула о вхождении слов B) Для слов применить стеммирование / лемматизацию / очистку от стоп-слов С) Реализовать индекс как LSM-подобное дерево
• Домашнее задание 3
  Взяв за основу индекс из задания 2, A) Реализовать поиск по префиксу B) Реализовать поиск по wildcard с помощью k-gram
• Домашнее задание 4
  Взяв за основу индекс из задания 2, A) Для каждого документа задать дополнительно атрибут даты и искать по диапазону дат, а также по булевым формулам, содержащим условия на диапазоны дат B) Пусть у документа присутствуют две даты: начала и окончания жизни (последняя может быть не задана). Реализовать поиск документов, - валидных в диапазоне дат - появившихся в диапазоне дат
• Домашнее задание 5
  Построить позиционный индекс, что позволит выполнять фразовый поиск по документам.
• Домашнее задание 6
  Реализовать FM-index для поиска по подстроке и тесты к нему.
• Домашнее задание 7
  Реализовать k-d tree / R-tree и бенчмарк для поиска ближайшего соседа в k-мерном пространстве. Показать, как меняется скорость поиска с ростом параметра k.
• Домашнее задание 8
  Построить индекс, что позволит давать ранжированные результаты A) по TF-IDF B) согласно модели векторного пространства С) реализовать эффективное “Inexact top K” ранжирование
• Домашнее задание 9
  Построить индекс для dense vector (similarity) search, используя BERT для получения эмбеддингов А) используя Faiss для поиска. B) понижая размерность самостоятельно (randomized PCA, LSH, кластеризация, etc).
• Экзамен
  Экзамен проводится в устной форме на платформе Zoom. Студент получает билет, который включает в себя два вопроса из программы экзамена, с учётом ранее сданных домашних заданий. Во время подготовки можно использовать любые печатные материалы, но запрещается использовать электронные средства коммуникации. После ответа студенту могут быть заданы дополнительные вопросы по программе курса.

Промежуточная аттестация

• 2024/2025 2nd module
  Для зачёта нужно сдать минимум 2 задачи. Студенты, не сдавшие двух задач (с соответствующей теорией в беседе с преподавателем), до зачёта не допускаются. Три балла за домашнее задание дают удовлетворительно (4) автоматом и возможность получить отметку вплоть до хорошо (7) включительно, в зависимости от баллов на экзамене. Пять баллов дают хорошо (6) автоматом и возможность получить вплоть до отлично (8), в зависимости от баллов на экзамене. Семь баллов – хорошо (7) автоматом, отметка до отлично (9) на экзамене. Восемь баллов — отлично (8) автоматом, отметка до отлично (10) на экзамене.

Список литературы

Рекомендуемая основная литература

• Petrov, A., & O’Reilly for Higher Education (Firm). (2019). Database Internals : A Deep Dive Into How Distributed Data Systems Work (Vol. First edition). Sebastopol, CA: O’Reilly Media. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=2250514

Рекомендуемая дополнительная литература

• Kleppmann, M. (2017). Designing Data-Intensive Applications : The Big Ideas Behind Reliable, Scalable, and Maintainable Systems. Sebastopol, CA: O’Reilly Media. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=1487643

Авторы

• Кононова Елизавета Дмитриевна