Пе́рший за́сік лі́пший () — це алгоритм пошуку, розроблений для ефективного знаходження наближеного розв'язку задачі пошуку найближчого сусіда у просторах дуже великої вимірності. Цей алгоритм ґрунтується на видозміні алгоритму пошуку k-вимірним деревом, що уможливлює індексування просторів більшої вимірності. Перший засік ліпший — це приблизний алгоритм, який повертає найближчого сусіда для великої частки запитів, і дуже близького сусіда в інших випадках.
Відмінності від k-вимірного дерева
Засіки переглядають у порядку збільшення відстані від точки запиту. Відстань до засіку визначають як мінімальну відстань до будь-якої точки його межі. Це втілюють за допомогою черги з пріоритетом.Shape Indexing Using Approximate Nearest-Neighbour Search in High-Dimensional Spaces, pp. 4-5 Знаходять фіксовану кількість найближчих кандидатів, і зупиняються. Типове прискорення — на два порядки.
Примітки