@inproceedings{DBLP:conf/sigmod/BeckerSW91, author = {Bruno Becker and Hans-Werner Six and Peter Widmayer}, editor = {James Clifford and Roger King}, title = {Spatial Priority Search: An Access Technique for Scaleless Maps}, booktitle = {Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data, Denver, Colorado, May 29-31, 1991}, publisher = {ACM Press}, year = {1991}, pages = {128-137}, ee = {http://doi.acm.org/10.1145/115790.115805, db/conf/sigmod/BeckerSW91.html}, crossref = {DBLP:conf/sigmod/91}, bibsource = {DBLP, http://dblp.uni-trier.de} }BibTeX
In geographic information systems, an important goal is the maintenance of seamless, scaleless maps. The amount of detail desired on a map decreases with decreasing scale. Cartographic techniques called generalization define the representations of geographic objects, depending on the scale. While generalization as a whole is considered an art, simple automatic generalization techniques exist for simple geometric objects. For polygonal lines and polygons, simplification techniques assign priorities to points. A map at a desired scale is then obtained by ignoring all points of sufficiently low priority. This implies that a geometric object appears on a map only if its priority is high enough, and also that an object is represented only by those of its defining points that have sufficiently high priority. The efficiency of retrieving a map of some area at a certain scale ideally should only depend on the amount of data retrieved.
In this paper, we present algorithms and a fully adaptive data structure that efficiently supports insertions, deletions, updates and geometric queries at an arbitrary location for an arbitrary scale. Our data structure adapts to dynamically changing data in such a way that objects outside the query area or of irrelevant priority do not influence the efficiency of the query substantially. The structure is of broader interest, because it supports general proximity queries with priority threshold for non-zero size geometric objects.
Furthermore, we show how to partition polygon corner points of different priorities such that they can be stored in the structure with practically no redundancy, and polygons for any priority threshold can be reassembled easily. A performance evaluation of our implementation with topographic data reveals that a performance gain of a high factor can be achieved with the structure under realistic assumptions.
Copyright © 1991 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.
CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...