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

Эта статья о структуре данных. Чтобы узнать о типе метрического пространства, см. Реальное дерево .

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

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

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

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

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

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

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

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

• Matlab : Деревья метрик реализованы в metricTree Класс, который является частью Военно-морской исследовательской лаборатории США бесплатной библиотеки компонентов трекера .