Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Бағыт нүктесі ағашы (немесе VP ағашы) — метрикалық кеңістіктегі деректерді орынды ("бағыт нүктесі") таңдап, деректерді екіге бөлу арқылы саралайтын метрикалық ағаш: бағыт нүктесіне белгілі бір шектен жақын нүктелер мен одан алыс нүктелер. Бұл әдіс деректерді үнемі кішірейтіп бөлу үшін рекурсивті түрде қолданылады, нәтижесінде ағаш құрылымы пайда болады, онда ағаштағы жақын нүктелер кеңістікте де жақын болуы мүмкін. Осының бір түрі — көп бағыт нүктесі ағашы (немесе MVP ағашы): үлкен метрикалық кеңістіктерден объектілерді ұқсастық іздеу сұраныстары үшін индекстеуге арналған дерек құрылымы. Ол әр деңгейді бөлу үшін бірнеше нүкте қолданады.
A vantage point tree (or VP tree) is a metric tree that segregates data in a metric space by choosing a position in the space (the "vantage point") and partitioning the data points into two parts: those points that are nearer to the vantage point than a threshold, and those points that are not. By recursively applying this procedure to partition the data into smaller and smaller sets, a tree data structure is created where neighbors in the tree are likely to be neighbors in the space. One generalization is called a multi vantage point tree (or MVP tree): a data structure for indexing objects from large metric spaces for similarity search queries. It uses more than one point to partition each level.
Тарих
Питер Йианилос бұрыштық ағашты ол (Питер Йианилос) және Джеффри Ульман дербес ашқандарын мәлімдеді. Ульман бұл деректер құрылымын метрикалық ағаш деп атады, ал VP ағашының атауын Йианилос ұсынды. Вантаж нүктесі ағаштары Нейльсен және авторлар тобы Брегман дивергенциясын қолдана отырып, метрикалық емес кеңістіктерге жалпыланды. Бұл итеративтік бөлу процесі k d ағашына ұқсас, бірақ тікбұрышты емес, дөңгелек (немесе сфералық, гиперсфералық және т.б.) бөлімдерді пайдаланады. Екі өлшемді Евклид кеңістігінде бұл деректерді бөлетін шеңберлер тізбегі ретінде визуализацияланады. Вантаж нүктесі ағашы стандартты емес метрикалық кеңістіктегі деректерді метрикалық ағаштарға бөлу үшін ерекше пайдалы.
Peter Yianilos claimed that the vantage point tree was discovered independently by him (Peter Yianilos) and by Jeffrey Uhlmann. Uhlmann called the data structure a metric tree, the name VP tree was proposed by Yianilos. Vantage point trees have been generalized to non metric spaces using Bregman divergences by Nielsen et al. This iterative partitioning process is similar to that of a k d tree, but uses circular (or spherical, hyperspherical, etc.) rather than rectilinear partitions. In two dimensional Euclidean space, this can be visualized as a series of circles segregating the data. The vantage point tree is particularly useful in dividing data in a non standard metric space into a metric tree.
Басты көзге қарау ағашын түсіну
Көрініс бұтағы деректерді сақтау әдісін шеңбер түрінде бейнелеуге болады.
The way a vantage point tree stores data can be represented by a circle.
Ағаштан іздеу
Нысанның ең жақын көршісін табу үшін нұсқаулық нүкте ағашын қолдануға болады. Іздеу алгоритмі рекурсивті. Кез келген қадамда біз v нүктесі мен t шектік қашықтығы бар ағаш түйінімен жұмыс істейміз. Қызығушылықтың x нүктесі нұсқаулық нүкте v-ден белгілі бір қашықтықта болады. Егер осы қашықтық d, t-ден кіші болса, онда алгоритмді рекурсивті түрде пайдаланып, нұсқаулық нүктеге t шегінен жақын нүктелерді қамтитын түйіннің кіші ағашын іздеңіз; әйтпесе, нұсқаулық нүктеден t шегінен алыс нүктелерді қамтитын түйіннің кіші ағашына рекурсия жасаймыз. Егер алгоритмді рекурсивті пайдалану x-ке дейінгі қашықтығы кішірек болатын көрші нүкте n-ді табатын болса, онда ол осы түйіннің екінші кіші ағашын іздеуге қажеттілік тудырмайды; табылған n түйіні қайтарылады. Әйтпесе, екінші кіші ағашты да рекурсивті іздеу қажет. Осыған ұқсас тәсіл нысанның x-тің k ең жақын көршілерін табу үшін де қолданылады. Рекурсияда, егер осы уақытқа дейін табылған ең жақын көршілердің тек k′ (< k) ғана қашықтығы кіші болса, онда екінші кіші ағашта x нүктесінің k - k′ ең жақын көршілері ізделеді.
A vantage point tree can be used to find the nearest neighbor of a point x. The search algorithm is recursive. At any given step we are working with a node of the tree that has a vantage point v and a threshold distance t. The point of interest x will be some distance from the vantage point v. If that distance d is less than t then use the algorithm recursively to search the subtree of the node that contains the points closer to the vantage point than the threshold t; otherwise recurse to the subtree of the node that contains the points that are farther than the vantage point than the threshold t. If the recursive use of the algorithm finds a neighboring point n with distance to x that is less than then it cannot help to search the other subtree of this node; the discovered node n is returned. Otherwise, the other subtree also needs to be searched recursively. A similar approach works for finding the k nearest neighbors of a point x. In the recursion, the other subtree is searched for k − k′ nearest neighbors of the point x whenever only k′ (< k) of the nearest neighbors found so far have distance that is less than .
Көзқарас нүктесі ағашының артықшылықтары
Индекс құрылғанға дейін домен үшін көпөлшемді нүктелерді болжаудың орнына, біз индексті тікелей қашықтық негізінде құрастырамыз. Осылай істеу алдын ала өңдеу қадамдарынан құтылуға мүмкіндік береді. Қарап тұруға ыңғайлы нүктелер ағашын жаңарту, FastMap әдісімен салыстырғанда салыстырмалы түрде оңай. FastMap үшін деректерді қосу немесе жою кезінде, FastMap өзін қайта сканерлеуі қажет болатын сәт туындайды. Бұл көп уақытты қажет етеді және қайта сканерлеудің қашан басталатынын анықтау қиын. Қашықтыққа негізделген әдістер икемді. Олар белгілі бір өлшемдер санындағы белгі векторлары түрінде ұсынылған объектілерді индекстеуге қабілетті.
Instead of inferring multidimensional points for domain before the index being built, we build the index directly based on the distance. Doing this, avoids pre processing steps. Updating a vantage point tree is relatively easy compared to the FastMap approach. For FastMap, after inserting or deleting data, there will come a time when FastMap will have to rescan itself. That takes up too much time and it is unclear to know when the rescanning will start. Distance based methods are flexible. It is “able to index objects that are represented as feature vectors of a fixed number of dimensions."
Күрделілігі
Қарап тұруға арналған ағаш құрудың уақыт шығыны шамамен O(n log n) тең. Әр элемент үшін ағаш log n деңгеймен төмен түсіріліп, оның орналасуы анықталады. Бірақ k тұрақты коэффициенті бар, мұнда k – ағаш түйініне арналған қарап тұру нүктелерінің саны. Бір жақын көршіні табу үшін қарап тұру нүктесі ағашын іздеудің уақыт шығыны O(log n) болып табылады. Log n деңгей бар, олардың әрқайсысы k қашықтық есептеуді қамтиды, мұнда k – ағаштағы сол позициядағы қарап тұру нүктелерінің (элементтердің) саны. Ауқымды іздеудің уақыт шығыны, бұл ең маңызды қасиет болуы мүмкін, қолданылатын алгоритмнің ерекшеліктері мен параметрлеріне байланысты айтарлықтай өзгеруі мүмкін. Бриннің мақаласында қашықтық есептеулер санымен өлшенген шығынды зерттеу үшін әртүрлі параметрлері бар бірнеше қарап тұру алгоритмдерімен жүргізілген тәжірибелердің нәтижелері келтірілген. Қарап тұруға арналған ағаштың орындық шығыны шамамен n тең. Әр элемент сақталады, және әрбір жапырақ емес түйіндегі ағаш элементі өзінің ұрпақ түйіндеріне сілтемелерді қажет етеді. (Бір іске асыру таңдауы туралы толық мәліметтерді Бриннен қараңыз. Түйіндегі элементтер санының параметрі маңызды рөл атқарады.) n нүкте болғанда, нүктелер арасындағы O(n²) жұптық қашықтықтар болады. Дегенмен, қарап тұру нүктесі ағашын құру үшін тек O(n log n) қашықтықты нақты есептеу қажет, ал іздеу үшін тек O(log n) қашықтық есептеуі талап етіледі. Мысалы, егер x және y нүктелер болса және d(x, y) қашықтығы кішкентай болса, онда x-тен алыс кез келген z нүктесі де y-ден шамамен сондай алыс болады, себебі метрикалық кеңістіктің үшбұрыш теңсіздігі d(y, z) ≥ d(x, z) − d(x, y) шартын береді.
The time cost to build a vantage point tree is approximately O(n log n). For each element, the tree is descended by log n levels to find its placement. However there is a constant factor k where k is the number of vantage points per tree node. The time cost to search a vantage point tree to find a single nearest neighbor is O(log n). There are log n levels, each involving k distance calculations, where k is the number of vantage points (elements) at that position in the tree. The time cost to search a vantage point tree for a range, which may be the most important attribute, can vary greatly depending on the specifics of the algorithm used and parameters. Brin's paper gives the result of experiments with several vantage point algorithms with various parameters to investigate the cost, measured in number of distance calculations. The space cost for a vantage point tree is approximately n. Each element is stored, and each tree element in each non leaf node requires a pointer to its descendant nodes. (See Brin for details on one implementation choice. The parameter for number of elements at each node plays a factor.) With n points there are O(n^(2)) pairwise distances between points. However, the creation of a vantage point tree requires that only O(n log n) distances be calculated explicitly, and a search requires only O(log n) distance calculations. For example, if x and y are points and it is known that the distance d(x, y) is small then any point z that is far from x will also necessarily be almost as far from y because the metric space's triangle inequality gives d(y, z) ≥ d(x, z) − d(x, y).