ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Spatial Priority Search: An Access Technique for Scaleless Maps.

Bruno Becker, Hans-Werner Six, Peter Widmayer: Spatial Priority Search: An Access Technique for Scaleless Maps. SIGMOD Conference 1991: 128-137
@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

Abstract

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.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

James Clifford, Roger King (Eds.): Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data, Denver, Colorado, May 29-31, 1991. ACM Press 1991 BibTeX , SIGMOD Record 20(2), June 1991
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1020 KB]

References

[1]
...
[2]
Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331 BibTeX
[3]
...
[4]
Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269 BibTeX
[5]
Michael Freeston: Advances in the Design of the BANG File. FODO 1989: 322-338 BibTeX
[6]
...
[7]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
[8]
Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: Globally Order Preserving Multidimensional Linear Hashing. ICDE 1988: 572-579 BibTeX
[9]
Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: The R-File: An Efficient Access Structure for Proximity Queries. ICDE 1990: 372-379 BibTeX
[10]
...
[11]
...
[12]
...
[13]
...
[14]
...
[15]
...
[16]
...
[17]
Hans-Werner Six, Peter Widmayer: Spatial Searching in Geometric Databases. ICDE 1988: 496-503 BibTeX
[18]
...
[19]
...
[20]
...

Referenced by

  1. Maurício R. Mediano, Marco A. Casanova, Marcelo Dreux: V-Trees - A Storage Method for Long Vector Data. VLDB 1994: 321-330
  2. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:40:05 2009