Информационный поиск — различия между версиями
M8hew (обсуждение | вклад) |
M8hew (обсуждение | вклад) |
||
| (не показано 13 промежуточных версии этого же участника) | |||
| Строка 2: | Строка 2: | ||
Осенний курс по выбору для студентов 4 курсов ПМИ ФКН ВШЭ. | Осенний курс по выбору для студентов 4 курсов ПМИ ФКН ВШЭ. | ||
| + | |||
| + | Занятия проводятся онлайн по вторникам в 18:10 в [https://us06web.zoom.us/j/9624371278?pwd=WEN6a2hvaU9pR0xpalY2T3JHV0QwUT09 zoom] | ||
'''Лектор''': Алексей Неганов aka [https://t.me/bokareis @bokareis]. | '''Лектор''': Алексей Неганов aka [https://t.me/bokareis @bokareis]. | ||
| − | + | '''Записи пар''': TBD | |
| − | + | '''Текущая ведомость''': TBD | |
== Формула оценки == | == Формула оценки == | ||
| Строка 13: | Строка 15: | ||
Оценка за курс состоит из оценки за задачи и зачета. | Оценка за курс состоит из оценки за задачи и зачета. | ||
| − | Чтобы быть допущенным к зачету балл за задачи должен быть минимум 2.0 | + | Чтобы быть допущенным к зачету балл за задачи должен быть минимум 2.0 |
| − | 3.0 за задачи — удовлетворительная отметка(4 балла) автоматом, | + | 3.0 за задачи — удовлетворительная отметка(4 балла) автоматом, можно получить "хорошо" на зачёте <br> |
| − | 5.0 — хорошо (6 баллов) автоматом, | + | 5.0 — хорошо (6 баллов) автоматом, можно получить "отлично" (8 баллов) <br> |
| − | 8.0 — отлично (8 баллов) автоматом, | + | 8.0 — отлично (8 баллов) автоматом, можно получить максимум <br> |
== Домашние задания == | == Домашние задания == | ||
| − | Домашние задания можно желательно сдавать на C/C++, Python, Go | + | Домашние задания можно желательно сдавать на C/C++, Python, Go <br> |
Допустимо на Java, C# | Допустимо на Java, C# | ||
| Строка 43: | Строка 45: | ||
'''Задание 3''' | '''Задание 3''' | ||
| − | Взяв за основу индекс из задания | + | Взяв за основу индекс из задания 2: |
# Реализовать поиск по префиксу | # Реализовать поиск по префиксу | ||
# Реализовать поиск по wildcard с помощью k-gram | # Реализовать поиск по wildcard с помощью k-gram | ||
| Строка 51: | Строка 53: | ||
'''Задание 4''' | '''Задание 4''' | ||
| − | + | Взяв за основу индекс из задания 2: | |
| − | + | ||
| − | Взяв за основу индекс из задания | + | |
# Для каждого документа задать дополнительно атрибут даты и искать по диапазону дат, а так же по булевым формулам, содержащим условия на диапазоны дат | # Для каждого документа задать дополнительно атрибут даты и искать по диапазону дат, а так же по булевым формулам, содержащим условия на диапазоны дат | ||
# Пусть у документа присутствуют две даты: начала и окончания жизни (последняя может быть не задана). Реализовать поиск документов, | # Пусть у документа присутствуют две даты: начала и окончания жизни (последняя может быть не задана). Реализовать поиск документов, | ||
| Строка 62: | Строка 62: | ||
'''Задание 5''' | '''Задание 5''' | ||
| − | |||
| − | |||
Построить позиционный индекс, что позволит выполнять фразовый поиск по документам. | Построить позиционный индекс, что позволит выполнять фразовый поиск по документам. | ||
| Строка 70: | Строка 68: | ||
'''Задание 6''' | '''Задание 6''' | ||
| − | |||
| − | |||
Реализуйте FM-index для поиска по подстроке и тесты к нему. | Реализуйте FM-index для поиска по подстроке и тесты к нему. | ||
| Строка 78: | Строка 74: | ||
'''Задание 7''' | '''Задание 7''' | ||
| − | |||
| − | |||
Построить индекс, что позволит давать ранжированные результаты | Построить индекс, что позволит давать ранжированные результаты | ||
| Строка 89: | Строка 83: | ||
'''Задание 8''' | '''Задание 8''' | ||
| − | |||
| − | |||
Построить индекс для dense vector (similarity) search, используя BERT для получения эмбеддингов | Построить индекс для dense vector (similarity) search, используя BERT для получения эмбеддингов | ||
| Строка 99: | Строка 91: | ||
'''Задание 9''' | '''Задание 9''' | ||
| − | |||
| − | |||
Реализуйте k-d tree и бенчмарк для поиска точки в k-мерном пространстве. Покажите, как меняется скорость поиска с ростом параметра k. | Реализуйте k-d tree и бенчмарк для поиска точки в k-мерном пространстве. Покажите, как меняется скорость поиска с ростом параметра k. | ||
| Строка 108: | Строка 98: | ||
== Литература == | == Литература == | ||
| − | + | * 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. | ||
Текущая версия на 23:15, 8 ноября 2024
Основы информационного поиска
Осенний курс по выбору для студентов 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.
- Построить индекс (хотя бы в памяти), что позволит выдавать документы, для которых верна булева формула о вхождении слов
- Для слов применить стеммирование / лемматизацию / очистку от стоп-слов
- Реализовать индекс как LSM-подобное дерево
Deadline: 25 октября
Задание 3
Взяв за основу индекс из задания 2:
- Реализовать поиск по префиксу
- Реализовать поиск по wildcard с помощью k-gram
Deadline: 10 ноября
Задание 4
Взяв за основу индекс из задания 2:
- Для каждого документа задать дополнительно атрибут даты и искать по диапазону дат, а так же по булевым формулам, содержащим условия на диапазоны дат
- Пусть у документа присутствуют две даты: начала и окончания жизни (последняя может быть не задана). Реализовать поиск документов,
- валидных в диапазоне дат
- появившихся в диапазоне дат
Deadline: 17 ноября
Задание 5
Построить позиционный индекс, что позволит выполнять фразовый поиск по документам.
Deadline: 24 ноября
Задание 6
Реализуйте FM-index для поиска по подстроке и тесты к нему.
Deadline: 1 декабря
Задание 7
Построить индекс, что позволит давать ранжированные результаты
- по TF-IDF
- согласно модели векторного пространства
- реализовать эффективное Inexact top K ранжирование
Deadline: 8 декабря
Задание 8
Построить индекс для dense vector (similarity) search, используя BERT для получения эмбеддингов
- используя Faiss для поиска
- понижая размерность самостоятельно (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.
