Эффективные алгоритмы нахождения ближайших соседей среди миллиардов векторов в пространствах высокой размерности

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