Prioritet R-träd

Prioritets -R-trädet är ett värsta asymptotiskt optimalt alternativ till det rumsliga trädet R-trädet . Det föreslogs först av Arge, De Berg, Haverkort och Yi, K. i en artikel från 2004. Det prioriterade R-trädet är i huvudsak en hybrid mellan ett k-dimensionellt träd och ett r-träd genom att det definierar ett givet objekts N -dimensionell begränsningsvolym (kallad Minimum Bounding Rectangles - MBR) som en punkt i N-dimensioner, representerad av det ordnade paret av rektanglarna. Termen prioriterad kommer från introduktionen av fyra prioritetsblad som representerar de mest extrema värdena för varje dimension, inkluderad i varje gren av trädet. Innan man svarar på en fönsterfråga genom att korsa undergrenarna, kontrollerar det prioriterade R-trädet först efter överlappning i sina prioritetsnoder. Undergrenarna korsas (och konstrueras) genom att kontrollera om det minsta värdet av den första dimensionen i frågan är över värdet för undergrenarna. Detta ger tillgång till en snabb indexering med värdet av den första dimensionen av begränsningsrutan.

Prestanda

Arge et al. skriver att prioritetsträdet alltid svarar på fönsterfrågor med $\displaystyle O\left(\left({\frac {N}{B}}\right)^{ 1-{\frac {1}{d}}}+{\frac {T}{B}}\right)}$ I/Os, där N är antalet d-dimensionella (hyper-) rektanglar lagrade i R -träd, B är diskblockets storlek och T är utdatastorleken.

Mått

I fallet med $d=2$ representeras rektangeln av $\,( (x_{min},y_{min}),(x_{max},y_{max}))$ och MBR alltså fyra hörn $\,(x_{min},y_{min},x_{max},y_{max})$ .

Se även

• Begränsande volymhierarki
• B-träd
• R-träd