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

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

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

Занятия проводятся онлайн по вторникам в 18:10 в zoom

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

Записи пар: TBD

Текущая ведомость: TBD

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

Оценка за курс состоит из оценки за задачи и зачета.

Чтобы быть допущенным к зачету балл за задачи должен быть минимум 2.0

3.0 за задачи — удовлетворительная отметка(4 балла) автоматом, можно получить "хорошо" на зачёте
5.0 — хорошо (6 баллов) автоматом, можно получить "отлично" (8 баллов)
8.0 — отлично (8 баллов) автоматом, можно получить максимум

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

Домашние задания можно желательно сдавать на C/C++, Python, Go
Допустимо на Java, C#

Задание 1

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

Deadline: 18 октября

Задание 2

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

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

Deadline: 25 октября

Задание 3

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

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

Deadline: 10 ноября

Задание 4

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

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

Deadline: 17 ноября

Задание 5

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

Deadline: 24 ноября

Задание 6

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

Deadline: 1 декабря

Задание 7

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

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

Deadline: 8 декабря

Задание 8

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

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

Deadline: 15 декабря

Задание 9

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

Deadline: 22 декабря

Литература

• Petrov, A. (2019). Database Internals: A deep dive into how distributed data systems work.
• Luo, C., & Carey, M. J. (2020). LSM-based storage techniques: a survey.
• Schütze, H., Manning, C. D., & Raghavan, P. (2008). Introduction to information retrieval.
• Lemire, D., Ssi‐Yan‐Kai, G., & Kaser, O. (2016). Consistently faster and smaller compressed bitmaps with roaring.
• Grabowski, S., Raniszewski, M., & Deorowicz, S. (2017). FM-index for Dummies.
• Navarro, G., & Mäkinen, V. (2007). Compressed full-text indexes.