Перший засік ліпший
Пе́рший за́сік лі́пший (англ. best bin first) — це алгоритм пошуку, розроблений для ефективного знаходження наближеного розв'язку задачі пошуку найближчого сусіда у просторах дуже великої вимірності. Цей алгоритм ґрунтується на видозміні алгоритму пошуку k-вимірним деревом, що уможливлює індексування просторів більшої вимірності. Перший засік ліпший — це приблизний алгоритм, який повертає найближчого сусіда для великої частки запитів, і дуже близького сусіда в інших випадках.[1]
Відмінності від k-вимірного дерева
ред.- Засіки переглядають у порядку збільшення відстані від точки запиту. Відстань до засіку визначають як мінімальну відстань до будь-якої точки його межі. Це втілюють за допомогою черги з пріоритетом.[2]
- Знаходять фіксовану кількість найближчих кандидатів, і зупиняються.
- Типове прискорення — на два порядки.
Примітки
ред.- ↑ Beis, J.; Lowe, D. G. (1997). Shape indexing using approximate nearest-neighbour search in high-dimensional spaces. Conference on Computer Vision and Pattern Recognition. Puerto Rico. с. 1000—1006. CiteSeerX 10.1.1.23.9493. (англ.)
- ↑ Shape Indexing Using Approximate Nearest-Neighbour Search in High-Dimensional Spaces, pp. 4-5 (англ.)
|
Це незавершена стаття про алгоритми. Ви можете допомогти проєкту, виправивши або дописавши її. |