Введение
структура данных
Метрическое дерево – это любая древовидная структура данных, предназначенная для индексации данных в метрических пространствах. Метрические деревья используют свойства метрических пространств, такие как неравенство треугольника, для повышения эффективности доступа к данным. Примеры включают M-дерево, vp-деревья, деревья покрытий, MVP-деревья и BK-деревья.
Многомерный поиск
Большинство алгоритмов и структур данных для поиска в наборе данных основаны на классическом алгоритме бинарного поиска, а обобщения, такие как k-d дерево или дерево отрезков, работают путем чередования алгоритма бинарного поиска по отдельным координатам и рассмотрения каждой пространственной координаты как независимого ограничения поиска. Эти структуры данных хорошо подходят для задач поиска по диапазону, требующих найти все точки, удовлетворяющие заданным условиям. Ограничением этих многомерных структур поиска является то, что они определены только для поиска объектов, которые можно рассматривать как векторы. Они неприменимы к более общему случаю, когда алгоритму предоставлен только набор объектов и функция для измерения расстояния или сходства между двумя объектами. Например, если кто-то разработал функцию, возвращающую значение, указывающее степень сходства одного изображения с другим, то естественной алгоритмической задачей будет поиск в наборе данных изображений тех, которые, согласно этой функции, наиболее похожи на заданное изображение запроса.
A limitation of these multidimensional search structures is that they are only defined for searching over objects that can be treated as vectors. They aren't applicable for the more general case in which the algorithm is given only a collection of objects and a function for measuring the distance or similarity between two objects. If, for example, someone were to create a function that returns a value indicating how similar one image is to another, a natural algorithmic problem would be to take a dataset of images and find the ones that are similar according to the function to a given query image.
Структуры метрических данных
Если для измерения сходства не предусмотрена структура, то лучшим решением будет прямой перебор, требующий сравнения запросного изображения с каждым изображением в наборе данных. Однако, если функция сходства удовлетворяет неравенству треугольника, то результат каждого сравнения можно использовать для отсеивания кандидатов, подлежащих дальнейшему рассмотрению. Первая статья о метрических деревьях, а также первое публичное использование термина "метрическое дерево", была опубликована Джеффри Ульманном в 1991 году. Другие исследователи независимо работали над схожими структурами данных. В частности, Питер Йянилос утверждал, что независимо разработал тот же метод, который он назвал деревом опорных точек (VP-дерево). Исследования в области метрических деревьев получили значительное развитие в конце 1990-х годов и включали в себя изучение их применения к очень большим базам данных со стороны Сергея Брина, одного из основателей Google. Первый учебник по метрическим структурам данных был опубликован в 2006 году.