# External Memory Data Structures for 3 and 4-Sided Queries

In this paper, we experimentally evaluate the relative performance of 3 external memory query structures. The R and Priority R (PR) trees are compared using 4-sided rectangle queries in R^d. For 3-sided point queries in R^2, we compare the two structures mentioned above to the external priority search (EPS) tree. While the PR and EPS trees possess optimal I/O bounds, they are largely theoretical works. The R-tree, on the other hand, is a simpler heuristic data structure that is commonly used in practise but is inefficient in the worst case. After comparing wall times and I/O efficiency of queries, updates and bulk loads of the three structures on a variety of simulated and real data, we find the R-tree variants to generally outperform the EPS and PR trees in R^2. In higher dimensions, however, the PR-tree is most efficient.

Attachment | Size |
---|---|

CS-2005-17.pdf | 758.37 KB |