Информационный поиск — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
 
(не показано 16 промежуточных версии этого же участника)
Строка 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
  
−
Записи пар TBD
+
'''Текущая ведомость''': TBD
  
 
== Формула оценки ==  
 
== Формула оценки ==  
  
−
TBD
+
Оценка за курс состоит из оценки за задачи и зачета.
 +
 
 +
Чтобы быть допущенным к зачету балл за задачи должен быть минимум 2.0
 +
 
 +
3.0 за задачи — удовлетворительная отметка(4 балла) автоматом, можно получить "хорошо" на зачёте <br>
 +
5.0 — хорошо (6 баллов) автоматом, можно получить "отлично" (8 баллов) <br>
 +
8.0 — отлично (8 баллов) автоматом, можно получить максимум <br>
  
 
== Домашние задания ==
 
== Домашние задания ==
  
−
'''Задание 1'''
+
Домашние задания можно желательно сдавать на C/C++, Python, Go <br>
 +
Допустимо на Java, C#
  
−
''Языки: C, C++, Go''
+
'''Задание 1'''
  
 
Реализуйте LSM-дерево со строковыми ключами (levelled / tiered — на выбор). Дисковые компоненты должны поддерживать бинарный или иной логарифмический поиск без полной выгрузки в RAM. Обязательны Блум-фильтры для компонент.   
 
Реализуйте LSM-дерево со строковыми ключами (levelled / tiered — на выбор). Дисковые компоненты должны поддерживать бинарный или иной логарифмический поиск без полной выгрузки в RAM. Обязательны Блум-фильтры для компонент.   
Строка 32: Строка 41:
 
# Реализовать индекс как LSM-подобное дерево
 
# Реализовать индекс как LSM-подобное дерево
  
 +
''Deadline: 25 октября''
  
 
'''Задание 3'''
 
'''Задание 3'''
  
−
Взяв за основу индекс из задания 4:
+
Взяв за основу индекс из задания 2:
 
# Реализовать поиск по префиксу
 
# Реализовать поиск по префиксу
 
# Реализовать поиск по wildcard с помощью k-gram
 
# Реализовать поиск по wildcard с помощью k-gram
  
−
'''Задание 4'''
+
''Deadline: 10 ноября''
  
−
''Языки: С, С++, Go, Python''
+
'''Задание 4'''
  
−
Взяв за основу индекс из задания 4:
+
Взяв за основу индекс из задания 2:
 
# Для каждого документа задать дополнительно атрибут даты и искать по диапазону дат, а так же по булевым формулам, содержащим условия на диапазоны дат
 
# Для каждого документа задать дополнительно атрибут даты и искать по диапазону дат, а так же по булевым формулам, содержащим условия на диапазоны дат
 
# Пусть у документа присутствуют две даты: начала и окончания жизни (последняя может быть не задана). Реализовать поиск документов,
 
# Пусть у документа присутствуют две даты: начала и окончания жизни (последняя может быть не задана). Реализовать поиск документов,
Строка 49: Строка 59:
 
#* появившихся в диапазоне дат  
 
#* появившихся в диапазоне дат  
  
−
'''Задание 5'''
+
''Deadline: 17 ноября''
  
−
''Языки: С, С++, Go, Python''
+
'''Задание 5'''
  
 
Построить позиционный индекс, что позволит выполнять фразовый поиск по документам.
 
Построить позиционный индекс, что позволит выполнять фразовый поиск по документам.
 +
 +
''Deadline: 24 ноября''
  
 
'''Задание 6'''
 
'''Задание 6'''
−
 
−
''Языки: Go, Python''
 
  
 
Реализуйте FM-index для поиска по подстроке и тесты к нему.  
 
Реализуйте FM-index для поиска по подстроке и тесты к нему.  
 +
 +
''Deadline: 1 декабря''
  
 
'''Задание 7'''
 
'''Задание 7'''
−
 
−
''Языки: С, С++, Go, Python''
 
  
 
Построить индекс, что позволит давать ранжированные результаты
 
Построить индекс, что позволит давать ранжированные результаты
Строка 69: Строка 79:
 
# согласно модели векторного пространства
 
# согласно модели векторного пространства
 
# реализовать эффективное Inexact top K ранжирование
 
# реализовать эффективное Inexact top K ранжирование
 +
 +
''Deadline: 8 декабря''
  
 
'''Задание 8'''
 
'''Задание 8'''
  
−
''Языки: C, C++, Go''
+
Построить индекс для dense vector (similarity) search, используя BERT для получения эмбеддингов
 +
# используя Faiss для поиска
 +
# понижая размерность самостоятельно (randomized PCA, LSH, кластеризация, etc)
  
−
Реализуйте k-d tree и бенчмарк для поиска точки в k-мерном пространстве. Покажите, как меняется скорость поиска с ростом параметра k.
+
''Deadline: 15 декабря''
  
 
'''Задание 9'''
 
'''Задание 9'''
  
−
''Языки: С++, Python''
+
Реализуйте k-d tree и бенчмарк для поиска точки в k-мерном пространстве. Покажите, как меняется скорость поиска с ростом параметра k.
  
−
Построить индекс для dense vector (similarity) search, используя BERT для получения эмбеддингов
+
''Deadline: 22 декабря''
−
# используя Faiss для поиска
+
−
# понижая размерность самостоятельно (randomized PCA, LSH, кластеризация, etc)
+
  
 
== Литература ==
 
== Литература ==
  
−
TBD
+
* 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.

  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.
Источник — «http://wiki.cs.hse.ru/index.php?title=Информационный_поиск&oldid=87880»