Okładka drzewa

Drzewo okładek to rodzaj struktury danych w informatyce , który został specjalnie zaprojektowany w celu ułatwienia przyspieszenia wyszukiwania najbliższego sąsiada . Jest to udoskonalenie struktury danych Navigating Net i powiązane z różnymi innymi strukturami danych opracowanymi do indeksowania danych z natury niskowymiarowych.

Drzewo można traktować jako hierarchię poziomów, przy czym najwyższy poziom zawiera punkt główny, a dolny poziom zawiera każdy punkt w przestrzeni metrycznej. Każdy poziom C jest powiązany z wartością całkowitą i , która zmniejsza się o jeden w miarę opadania drzewa. Każdy poziom C w drzewie okładek ma trzy ważne właściwości:

• zagnieżdżanie: ${\ Displaystyle C_ {i} \ subseteq C_ {i-1}}$
• Pokrycie: $\ displaystyle p}$ każdego punktu istnieje punkt taki, $\ w C_ {i -1}$ odległość od $p$${$ jest mniejsze lub równe ${i}}$$\ displaystyle q}$ i dokładnie jeden taki jest rodzicem ${$ .
• $displaystyle$ : dla wszystkich punktów odległość od $\ displaystyle p, q \ in C_ {i}}$ jest większa niż ${\ displaystyle p}$ do $}$ .

Złożoność

Znajdować

Podobnie jak inne drzewa metryczne, drzewo okładki umożliwia wyszukiwanie najbliższego sąsiada w gdzie jest stałą związaną z $(\ eta * \ log {n})}$$Displaystyle$ wymiarowość zbioru danych, a n to liczność. $Dla$$,$ , podstawowe wyszukiwanie liniowe wymaga jest znacznie gorszą . Jednak w wielowymiarowych przestrzeniach metrycznych stała jest nietrywialna, co oznacza, że ​​nie można jej zignorować w analizie $.$ W przeciwieństwie do innych drzew metrycznych, drzewo pokrycia ma teoretyczną granicę swojej stałej, która jest oparta na stałej ekspansji zbioru danych lub stałej podwojenia (w przypadku przybliżonego wyszukiwania NN). Ograniczeniem $_$ gdzie $_$ _

Wstawić

Chociaż drzewa okładek zapewniają szybsze wyszukiwanie niż podejście naiwne, tę zaletę należy rozważyć z dodatkowymi kosztami utrzymania struktury danych. W naiwnym podejściu dodanie nowego punktu do zbioru danych jest trywialne, ponieważ porządek nie musi być zachowany, ale w drzewie tytułowym może zająć ${\ Displaystyle O (c ^ {6} \ log {n})}$ czas. Jest to jednak górna granica i wdrożono pewne techniki, które wydają się poprawiać wydajność w praktyce.

Przestrzeń

Drzewo okładki wykorzystuje niejawną reprezentację do śledzenia powtarzających się punktów. Zatem wymaga tylko przestrzeni O (n).

Zobacz też

• Wyszukiwanie najbliższego sąsiada
• kd-drzewo

Notatki

Bibliografia

• Alina Beygelzimer, Sham Kakade i John Langford. Drzewa osłonowe dla najbliższego sąsiada. w Proc. Międzynarodowa konferencja na temat uczenia maszynowego (ICML), 2006.
• Strona drzewa okładek JL . Strona Johna Langforda zawiera linki do dokumentów i kodu.
• Implementacja C++ Cover Tree w serwisie GitHub .
• Implementacja drzewa okładki w Javie.