Loading...
Please wait, while we are loading the content...
Similar Documents
I/O-efficient point location using persistent B-trees
| Content Provider | ACM Digital Library |
|---|---|
| Author | Arge, Lars Danner, Andrew Teh, Sha-Mayn |
| Copyright Year | 2003 |
| 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. |
| File Format | |
| ISSN | 10846654 |
| e-ISSN | 10846654 |
| DOI | 10.1145/996546.996549 |
| Journal | Journal of Experimental Algorithmics (JEA) |
| Volume Number | 8 |
| Language | English |
| Publisher | Association for Computing Machinery (ACM) |
| Publisher Date | 2003-12-01 |
| Publisher Place | New York |
| Access Restriction | One Nation One Subscription (ONOS) |
| Content Type | Text |
| Resource Type | Article |
| Subject | Theoretical Computer Science |
