External Memory Data Structures for 3 and 4-Sided Queries


Michal Lemczyk
Glenn Hickey
Michael Lawrence

Author Addresses: 

Faculty of Computer Science
Dalhousie University
6050 University Ave.
PO Box 15000
Halifax, Nova Scotia, Canada
B3H 4R2



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.

Tech Report Number: 
Report Date: 
October 10, 2005
PDF icon CS-2005-17.pdf758.37 KB