Метрическое дерево
-
Метрические деревья
- Специализированные древовидные структуры данных для индексации данных в пространствах метрик
- Используют свойства метрических пространств для эффективного доступа к данным
- Примеры: M-дерево, vp-деревья, покровные деревья, MVP-деревья, BK-деревья
-
Многомерный поиск
- Большинство алгоритмов и структур данных основаны на бинарном поиске
- Обобщения: дерево k-d, дерево диапазонов
- Подходят для задач запроса диапазона
- Ограничены поиском по объектам, рассматриваемым как векторы
-
Структуры метрических данных
- Поиск методом перебора требует сравнения каждого изображения в запросе с каждым изображением в наборе данных
- Если функция подобия удовлетворяет неравенству треугольника, можно сократить набор кандидатов
-
История и исследования
- Первая статья о метрических деревьях написана Джеффри Ульманом в 1991 году
- Питер Янилос независимо открыл метод, названный деревом точек обзора (VP-tree)
- Исследование метрических древовидных структур данных началось в конце 1990-х годов
- Первый учебник по метрическим структурам данных опубликован в 2006 году
-
Реализации с открытым исходным кодом
- Matlab: Метрические деревья реализованы в классе metricTree библиотеки Tracker Военно-морской исследовательской лаборатории США