R*-drzewo

R*-drzewo
Wynaleziony	1990
Wynalezione przez	Norbert Beckmann, Hans-Peter Kriegel , Ralf Schneider i Bernhard Seeger
Złożoność czasowa w notacji dużego O
Algorytm Przeciętny Najgorszy przypadek Przestrzeń O( n ) O( n ) Szukaj O(log n ) Wstawić O(log n )

W przetwarzaniu danych R*-drzewa są odmianą R-drzew używanych do indeksowania informacji przestrzennych. R*-drzewa mają nieco wyższy koszt budowy niż standardowe R-drzewa, ponieważ dane mogą wymagać ponownego wstawienia; ale wynikowe drzewo będzie zwykle miało lepszą wydajność zapytania. Podobnie jak standardowe drzewo R, może przechowywać zarówno dane punktowe, jak i przestrzenne. Został zaproponowany przez Norberta Beckmanna, Hansa-Petera Kriegela , Ralfa Schneidera i Bernharda Seegera w 1990 roku.

Różnica między R*-drzewami a R-drzewami

R*-Drzewo zbudowane przez wielokrotne wstawianie (w ELKI ). W tym drzewie występuje niewielkie nakładanie się, co zapewnia dobrą wydajność zapytań. Czerwone i niebieskie MBR to strony indeksu, zielone MBR to węzły liści.

Minimalizacja zarówno pokrycia, jak i nakładania się ma kluczowe znaczenie dla wydajności R-drzew. Nakładanie się oznacza, że ​​podczas zapytania lub wstawiania danych więcej niż jedna gałąź drzewa musi zostać rozwinięta (ze względu na sposób dzielenia danych na regiony, które mogą się nakładać). Zminimalizowane pokrycie poprawia wydajność przycinania, umożliwiając częstsze wykluczanie całych stron z wyszukiwania, w szczególności w przypadku zapytań o zakres ujemny. Drzewo R* próbuje zredukować oba, używając kombinacji poprawionego algorytmu podziału węzłów i koncepcji wymuszonego ponownego wstawienia przy przepełnieniu węzłów. Opiera się to na obserwacji, że struktury R-drzewa są bardzo podatne na kolejność, w jakiej ich wpisy są wstawiane, więc struktura wstawiona (a nie ładowana masowo) prawdopodobnie nie będzie optymalna. Usuwanie i ponowne wstawianie wpisów pozwala im „znaleźć” miejsce w drzewie, które może być bardziej odpowiednie niż ich pierwotna lokalizacja.

Gdy węzeł jest przepełniony, część jego wpisów jest usuwana z węzła i ponownie umieszczana w drzewie. (Aby uniknąć nieokreślonej kaskady ponownych wstawiania spowodowanej kolejnym przepełnieniem węzła, procedura ponownego wstawiania może być wywołana tylko raz na każdym poziomie drzewa podczas wstawiania dowolnego nowego wpisu). Efektem jest tworzenie lepiej skupionych grup wpisy w węzłach, zmniejszając pokrycie węzłów. Ponadto faktyczne podziały węzłów są często odkładane w czasie, co powoduje wzrost średniego zajętości węzłów. Ponowne wstawianie może być postrzegane jako metoda przyrostowej optymalizacji drzewa wyzwalanej w przypadku przepełnienia węzła.

Wydajność

• Ulepszona heurystyka podziału tworzy strony, które są bardziej prostokątne, a przez to lepsze dla wielu aplikacji.
• Metoda ponownego wstawiania optymalizuje istniejące drzewo, ale zwiększa złożoność.
• Skutecznie obsługuje jednocześnie dane punktowe i przestrzenne.

Wpływ różnych heurystyk podziału na bazę danych z niemieckimi okręgami pocztowymi

• 

  
  R-Tree z kwadratowym podziałem Guttmana. Istnieje wiele stron, które rozciągają się ze wschodu na zachód w całych Niemczech, a strony często się pokrywają. Nie jest to korzystne w przypadku większości aplikacji, które często wymagają tylko małego prostokątnego obszaru, który przecina się z wieloma plasterkami.

• 

  
  R-Tree z podziałem liniowym Ang-Tan. Chociaż plasterki nie rozciągają się tak daleko, jak w przypadku Guttmana, problem z krojeniem dotyczy prawie każdej strony liścia. Strony liści pokrywają się w niewielkim stopniu, ale strony katalogów tak.

• 

  
  Podział topologiczny drzewa R*. Strony zachodzą na siebie w bardzo niewielkim stopniu, ponieważ drzewo R* próbuje zminimalizować nakładanie się stron, a ponowne wstawienia jeszcze bardziej zoptymalizowały drzewo. Strategia podziału również nie preferuje plasterków, więc wynikowe strony są znacznie bardziej przydatne w typowych aplikacjach mapowych.

Algorytm i złożoność

• R*-tree używa tego samego algorytmu, co zwykłe R-drzewo dla operacji zapytań i usuwania.
• Podczas wstawiania drzewo R* wykorzystuje połączoną strategię. W przypadku węzłów liścia nakładanie się jest zminimalizowane, podczas gdy w przypadku węzłów wewnętrznych powiększenie i powierzchnia są zminimalizowane.
• Podczas podziału drzewo R* wykorzystuje podział topologiczny, który wybiera oś podziału na podstawie obwodu, a następnie minimalizuje nakładanie się.
• Oprócz ulepszonej strategii podziału, drzewo R* stara się również unikać podziałów poprzez ponowne wstawianie obiektów i poddrzew do drzewa, zainspirowane koncepcją równoważenia B- drzewa .

Złożoność zapytań i usuwania w najgorszym przypadku jest zatem identyczna z R-Tree. Strategia wstawiania do drzewa R * jest $}$ złożona niż strategia podziału liniowego $\ log$ ) drzewa R, ale mniej złożone niż strategia podziału kwadratowego ( ${\ Displaystyle {\ mathcal {O}} (M ^ {2})}$ ) dla rozmiaru strony ${\ displaystyle M}$ obiektów i ma niewielki wpływ na całkowitą złożoność. Całkowita złożoność wstawiania jest nadal porównywalna z drzewem R: ponowne wstawienia wpływają co najwyżej na jedną gałąź drzewa, a zatem ponowne wstawienia są porównywalne z ${\ Displaystyle {\ mathcal {O}} (\ log n)}$ wykonując podział na zwykłym R-drzewie. Ogólnie rzecz biorąc, złożoność drzewa R* jest taka sama jak zwykłego drzewa R.

Implementacja pełnego algorytmu musi uwzględniać wiele przypadków narożnych i sytuacji remisowych, które nie zostały tutaj omówione.

Linki zewnętrzne

• Media związane z R*-tree w Wikimedia Commons