Prioritní strom R - Priority R-tree

The Prioritní strom R je nejhorší asymptoticky optimální alternativa k prostorový strom R-strom. Poprvé to navrhli Arge, De Berg, Haverkort a Yi, K. v článku z roku 2004.^[1] Upřednostňovaný R-strom je v podstatě hybrid mezi a k-rozměrný strom a r-strom v tom, že definuje N-dimenzionální daný objekt mezní objem (nazývané Minimální ohraničující obdélníky - MBR) jako a směřovat v N-dimenzích, reprezentovaných uspořádanou dvojicí obdélníků. Termín upřednostněný pochází ze zavedení čtyř prioritních listů, které představují nejextrémnější hodnoty každé dimenze obsažené v každé větvi stromu. Před odpovědí a dotaz na okno procházením dílčích větví prioritní R-strom nejprve zkontroluje překrytí ve svých prioritních uzlech. Dílčí větve jsou procházeny (a konstruovány) kontrolou, zda je nejnižší hodnota první dimenze dotazu nad hodnotou dílčích větví. To umožňuje přístup k rychlé indexaci podle hodnoty první dimenze ohraničujícího rámečku.

Výkon

Arge a kol. píše, že prioritní strom vždy odpovídá na dotazy na okno${ displaystyle O left ( left ({ frac {N} {B}} right) ^ {1 - { frac {1} {d}}} + { frac {T} {B}} že jo)}$ I / O, kde N je počet d-rozměrných (hyper-) obdélníků uložených ve stromu R, B je velikost bloku disku a T je velikost výstupu.

Rozměry

V případě N = 2 je obdélník reprezentován ${ displaystyle , ((x_ {min}, y_ {min}), (x_ {max}, y_ {max}))}$ a MBR tedy čtyři rohy ${ displaystyle , (x_ {min}, y_ {min}, x_ {max}, y_ {max})}$.

Viz také

• Hraniční hierarchie svazků
• B-strom
• R-strom

Reference

Tento algoritmy nebo datové struktury související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.