We present an external planar point location data structure that is I/O-efficient both in theory and practice.

The developed structure uses linear space and answers a query in optimal $O(\log_B N)$ I/Os, where $B$ is the disk block size. It is based on a persistent B-tree, and all previously developed such structures assume a total order on the elements in the structure. As a theoretical result of independent interest, we show how to remove this assumption.

Most previous theoretical I/O-efficient planer point location structures are relatively complicated and have not been implemented. Based on a bucket approach, Vahrenhold and Hinrichs therefore developed a simple and practical, but theoretically non-optimal, heuristic structure. We present an extensive experimental evaluation that shows that on a range of real-world Geographic Information Systems (GIS) data, our structure uses fewer I/Os than the structure of Vahrenhold and Hinrichs to answer a query. On a synthetically generated worst-case dataset, our structure uses significantly fewer I/Os.

I/O-Efficient Point Location using Persistent B-trees.
ACM Journal of Experimental Algorithmics.

© Association for Computer Machinery and the Society for Industrial and Applied Mathematics 2003.