Лучшая корзина в первую очередь
(Перенаправлено с Best Bin First )
Best bin first — это алгоритм поиска , предназначенный для эффективного поиска приближенного решения задачи поиска ближайшего соседа в пространствах очень большой размерности. Алгоритм основан на варианте алгоритма поиска kd-дерева , который делает возможным индексирование пространств более высокой размерности. Лучший интервал — это приблизительный алгоритм, который возвращает ближайшего соседа для большой части запросов и очень близкого соседа в противном случае. [1]
Отличия от дерева кд
[ редактировать ]- Бины просматриваются в порядке возрастания расстояния от точки запроса. Расстояние до ячейки определяется как минимальное расстояние до любой точки ее границы. Это реализовано с помощью приоритетной очереди . [2]
- Найдите фиксированное количество ближайших кандидатов и остановитесь.
- Типично ускорение на два порядка.
Ссылки
[ редактировать ]- ^ Бейс, Дж.; Лоу, генеральный директор (1997). Индексация формы с использованием приблизительного поиска ближайших соседей в многомерных пространствах . Конференция по компьютерному зрению и распознаванию образов. Пуэрто-Рико. стр. 1000–1006. CiteSeerX 10.1.1.23.9493 .
- ^ Индексирование формы с использованием приблизительного поиска ближайших соседей в многомерных пространствах, стр. 4-5