Информационный поиск

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

Осенний курс по выбору для студентов 4 курсов ПМИ ФКН ВШЭ.

Лектор: Алексей Неганов aka @bokareis.

Чат курса TBD

Записи пар TBD

Формула оценки

TBD

Домашние задания

Задание 1

Языки: C, C++, Go

Реализуйте LSM-дерево со строковыми ключами (levelled / tiered — на выбор). Дисковые компоненты должны поддерживать бинарный или иной логарифмический поиск без полной выгрузки в RAM. Обязательны Блум-фильтры для компонент. Напишите бенчмарки для вставки, чтения по ключу, чтения короткого диапазона.

Deadline: 18 октября

Задание 2

Постройте обратный индекс для набора текстовых документов, используя Roaring bitmaps.

1. Построить индекс (хотя бы в памяти), что позволит выдавать документы, для которых верна булева формула о вхождении слов
2. Для слов применить стеммирование / лемматизацию / очистку от стоп-слов
3. Реализовать индекс как LSM-подобное дерево

Задание 3

Взяв за основу индекс из задания 4:

1. Реализовать поиск по префиксу
2. Реализовать поиск по wildcard с помощью k-gram

Задание 4

Языки: С, С++, Go, Python

Взяв за основу индекс из задания 4:

1. Для каждого документа задать дополнительно атрибут даты и искать по диапазону дат, а так же по булевым формулам, содержащим условия на диапазоны дат
2. Пусть у документа присутствуют две даты: начала и окончания жизни (последняя может быть не задана). Реализовать поиск документов,
   • валидных в диапазоне дат
   • появившихся в диапазоне дат

Задание 5

Языки: С, С++, Go, Python

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

Задание 6

Языки: Go, Python

Реализуйте FM-index для поиска по подстроке и тесты к нему.

Задание 7

Языки: С, С++, Go, Python

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

1. по TF-IDF
2. согласно модели векторного пространства
3. реализовать эффективное Inexact top K ранжирование

Задание 8

Языки: C, C++, Go

Реализуйте k-d tree и бенчмарк для поиска точки в k-мерном пространстве. Покажите, как меняется скорость поиска с ростом параметра k.

Задание 9

Языки: С++, Python

Построить индекс для dense vector (similarity) search, используя BERT для получения эмбеддингов

1. используя Faiss для поиска
2. понижая размерность самостоятельно (randomized PCA, LSH, кластеризация, etc)

Литература

TBD