 | The ACM Journal of Experimental Algorithmics |
Volume 7, Article 8, 2002
by
and
http://www.jea.acm.org/2002/VahrenholdLocation/
Abstract:
We present an algorithm for external memory planar point location
that is both effective and easy to implement. The base algorithm
is an external memory variant of the bucket method by Edahiro,
Kokubo and Asano that is combined with Lee and Yang's batched
internal memory algorithm for planar point location. Although our
algorithm is not optimal in terms of its worst-case behavior, we
show its efficiency for both batched and single-shot queries by
experiments with real-world data. The experiments show that the
algorithm benefits from the mainly sequential disk access pattern
and significantly outperforms the fastest algorithm for internal
memory. Due to its simple concept, the algorithm can take
advantage of multiple disks and processors in a rather
straightforward yet efficient way.
- Sources:
- The LaTeX version of the article;
this is a Unix file that contains the LaTeX source;
note that you must be a subscriber (institutional or individual) to access this file.
- The Postscript
version or PDF
version of the article;
note that you must be a subscriber (institutional or individual) to access
these files.
- The HTML version of the article;
note that you must be a subscriber (institutional or individual) to access
this file.
- The software suite accompanying the
article; this is a small Unix tar file, which includes the source code,
a Makefile, and the test files used in the article.
Received
|
Accepted
|
Final Revision
|
Published
|
|
|
|
|
Last updated and validated May 11, 2002, by editor@jea.acm.org