Access Restriction

Author Arge, Lars ♦ Danner, Andrew ♦ Teh, Sha-Mayn
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2003
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Abstract 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 $\textit{O}(log$ $\textit{BN})$ I/Os, where $\textit{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 planar 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 a similar number of I/Os as the structure of Vahrenhold and Hinrichs to answer a query. On a synthetically generated worst-case dataset our structure uses significantly fewer I/Os.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2003-12-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 8

Open content in new tab

   Open content in new tab
Source: ACM Digital Library