Алгоритмы нахождения ближайших соседей на больших массивах данных от Яндекса

В ближайший вторник, 22 ноября, на коллоквиуме Факультета компьютерных наук Высшей школы экономики выступит Артём Валерьевич Бабенко с докладом "Эффективные алгоритмы нахождения ближайших соседей среди миллиардов векторов в пространствах высокой размерности"

Определение ближайших соседей является подзадачей многих алгоритмов анализа данных, компьютерного зрения и других прикладных областей. Самый очевидный и наивный метод поиска ближайших соседей – полный перебор. Но при больших объемах поисковой базы полный перебор становится несостоятельным из-за своей вычислительной сложности, и необходимо использовать более быстрые приближенные алгоритмы. Одним из самых распространенных подходов является построение инвертированного индекса, который делит поисковое пространство на непересекающиеся регионы и осуществляет поиск только в небольшом количестве регионов, являющихся наиболее перспективными для конкретного запроса. В докладе будут описаны две структуры данных, обобщающие идею стандартного инвертированного индекса, позволяющие осуществлять поиск ближайших соседей в базах, содержащих миллиарды векторов, за несколько миллисекунд. Практическая применимость предложенных методов подтверждена экспериментально на нескольких поисковых базах из задач компьютерного зрения.

Для участников данного Форума, интересующихся поисковыми технологиями, данный доклад может быть интересным в том числе потому, что докладчик является представителем Яндекса.

Начало в 18 часов 10 минут.

Место проведения: 205-я аудитория ФКН ВШЭ, Москва, Кочновский проезд, дом 3.

Для посещения необходимо заказывать пропуск, это можно сделать по электронной почте computerscience@hse.ru.