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

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

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

Большинство алгоритмов и структур данных для поиска в наборе данных основаны на классическом алгоритме двоичного поиска , а такие обобщения, как дерево kd или дерево диапазонов , работают за счет чередования алгоритма двоичного поиска по отдельным координатам и обработки каждой пространственной координаты как независимого ограничения поиска. Эти структуры данных хорошо подходят для задач запроса диапазона , требующих каждую точку , удовлетворяющую условиям и . ${\displaystyle (x,y)}$ ${\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]

Рекомендации

1. Самет, Ханан (2006). Основы многомерных и метрических структур данных. Морган Кауфманн. ISBN 978-0-12-369446-1.
2. Ульманн, Джеффри (1991). «Выполнение общих запросов близости/сходства с помощью метрических деревьев». Письма об обработке информации . 40 (4): 175–179. дои :10.1016/0020-0190(91)90074-р.
3. Янилос, Питер Н. (1993). «Структуры данных и алгоритмы поиска ближайших соседей в общих метрических пространствах». Материалы четвертого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Общество промышленной и прикладной математики Филадельфии, Пенсильвания, США. стр. 311–321. pny93 . Проверено 7 марта 2019 г.
4. Брин, Сергей (1995). «Поиск ближайших соседей в больших метрических пространствах» (PDF) . 21-я Международная конференция по очень большим базам данных (VLDB) .
5. «Библиотека компонентов трекера». Репозиторий Матлаба . Проверено 5 января 2019 г.