Метрическое дерево

Метрика дерево любое дерево структура данных , специализирующихся на данных индексов в метрических пространствах . Деревья показателей используют свойства метрических пространств, такие как неравенство треугольника, чтобы сделать доступ к данным более эффективным. Примеры включают M-дерево , vp-деревья , деревья покрытия , MVP-деревья и BK-деревья . ^[1]

Многомерный поиск

Большинство алгоритмов и структур данных для поиска в наборе данных основаны на классическом алгоритме двоичного поиска , а такие обобщения, как дерево kd или дерево диапазонов, работают путем чередования алгоритма двоичного поиска по отдельным координатам и обработки каждой пространственной координаты как независимого ограничения поиска. Эти структуры данных хорошо подходят для задач запроса диапазона, запрашивая каждую точку, которая удовлетворяет и .${\ Displaystyle (х, у)}$${\ displaystyle {\ mbox {min}} _ {x} \ leq x \ leq {\ mbox {max}} _ {x}}$${\ displaystyle {\ mbox {min}} _ {y} \ leq y \ leq {\ mbox {max}} _ {y}}$

Ограничением этих многомерных структур поиска является то, что они определены только для поиска по объектам, которые можно рассматривать как векторы. Они не применимы для более общего случая, когда алгоритму предоставляется только набор объектов и функция для измерения расстояния или сходства между двумя объектами. Если, например, кто-то должен был создать функцию, которая возвращает значение, показывающее, насколько одно изображение похоже на другое, естественной алгоритмической проблемой было бы взять набор данных изображений и найти те, которые похожи по функции на данный запросить изображение.

Метрические структуры данных

Если для меры сходства нет структуры, тогда поиск методом грубой силы, требующий сравнения изображения запроса с каждым изображением в наборе данных, является лучшим, что можно сделать ^{[ необходима цитата ]} . Если, однако, функция подобия удовлетворяет неравенству треугольника, то можно использовать результат каждого сравнения для сокращения набора кандидатов, подлежащих проверке.

Первую статью о метрических деревьях, а также о первом использовании термина «метрическое дерево», опубликованном в открытой литературе, написал Джеффри Ульманн в 1991 году. ^[2] Другие исследователи независимо работали над подобными структурами данных. В частности, Петр Янилос утверждал, что независимо открыл тот же метод, который он назвал деревом точек обзора (VP-деревом). ^[3] Исследования структур данных в виде дерева показателей расцвели в конце 1990-х и включали в себя исследование соучредителем Google Сергеем Брином их использования для очень больших баз данных. ^[4] Первый учебник по метрическим структурам данных был опубликован в 2006 году. ^[1]

Реализации с открытым исходным кодом

• Matlab : деревья показателей реализованы в metricTreeклассе, который является частью бесплатной библиотеки компонентов трекера Лаборатории военно-морских исследований США . ^[5]

использованная литература