Der Priority R-tree

Wir präsentieren den Priority R-tree, oder PR-tree, der die erste R-tree-Variante ist, die immer eine Fensterabfrage mit O((N/B)1 1/d + T/B) I/O beantwortet, wobei N die Anzahl der d-dimensionalen (hyper-) Rechtecke ist, die im R-tree gespeichert sind, B die Blockgröße auf der Festplatte ist und T die Ausgabemenge. Dies ist asymptotisch optimal nachweislich und erheblich besser als andere R-tree-Varianten, bei denen eine Abfrage alle N/B Blätter im Baum besuchen kann, selbst wenn T = 0 ist. Wir präsentieren auch eine umfassende experimentelle Studie zur praktischen Leistung des PR-tree unter Verwendung sowohl realer als auch synthetischer Daten. Diese Studie zeigt, dass der PR-tree ähnlich wie die bekanntesten R-tree-Varianten bei realen und relativ gut verteilten Daten funktioniert, ihn jedoch bei extremeren Daten erheblich übertrifft.