Кіріспе
деректер құрылымы
Метрикалық ағаш – метрикалық кеңістіктердегі деректерді индекстеуге арналған кез келген ағаш деректер құрылымы. Метрикалық ағаштар деректерге қол жеткізуді тиімді ету үшін үшбұрыш теңсіздігі сияқты метрикалық кеңістіктердің қасиеттерін пайдаланады. Мысалдарға 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 жылы жарық көрді.