ACM SIGMOD Anthology VLDB dblp.uni-trier.de

A Raster Approximation For Processing of Spatial Joins.

Geraldo Zimbrao, Jano Moreira de Souza: A Raster Approximation For Processing of Spatial Joins. VLDB 1998: 558-569
@inproceedings{DBLP:conf/vldb/ZimbraoS98,
  author    = {Geraldo Zimbrao and
               Jano Moreira de Souza},
  editor    = {Ashish Gupta and
               Oded Shmueli and
               Jennifer Widom},
  title     = {A Raster Approximation For Processing of Spatial Joins},
  booktitle = {VLDB'98, Proceedings of 24rd International Conference on Very
               Large Data Bases, August 24-27, 1998, New York City, New York,
               USA},
  publisher = {Morgan Kaufmann},
  year      = {1998},
  isbn      = {1-55860-566-5},
  pages     = {558-569},
  ee        = {db/conf/vldb/ZimbraoS98.html},
  crossref  = {DBLP:conf/vldb/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The processing of spatial joins can be greatly improved by the use of filters that reduce the need for examining the exact geometry of polygons in order to find the intersecting ones. Approximations of candidate pairs of polygons are examined using such filters. As a result, three possible sets of answers are identified: the positive one, composed of intersecting polygon pairs; the negative one, composed of non- intersecting polygon pairs; and the inconclusive one, composed of theremaining pairs of candidates. To identify all the intersecting pairs of polygons with inconclusive answers, it is necessary to have access to the representation of polygons so that an exact geometry test can take place. This article presents a polygon approximation for spatial join processing which we call four-colors raster signature (4CRS). The performance of a filter using this approximation was evaluated with real world data sets. The results showed that our approach, when compared to other approaches presented in the related literature, reduced the inconclusive answers by a factor of more than two. As a result, the need for retrieving the representation of polygons and carrying out exact geometry tests is reduced by a factor of more than two, as well.

Copyright © 1998 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD DiSC

CDROM Version: Load the CDROM "DiSC, Volume 1 Number 1" and ...

ACM SIGMOD Anthology

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

Printed Edition

Ashish Gupta, Oded Shmueli, Jennifer Widom (Eds.): VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York City, New York, USA. Morgan Kaufmann 1998, ISBN 1-55860-566-5
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[BER96]
Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel: The X-tree : An Index Structure for High-Dimensional Data. VLDB 1996: 28-39 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BRI93a]
Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993: 237-246 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BRI93b]
Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider: Comparison of Approximations of Complex Objects Used for Approximation-based Query Processing in Spatial Database Systems. ICDE 1993: 40-49 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BRI94]
Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: Multi-Step Processing of Spatial Joins. SIGMOD Conference 1994: 197-208 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BRI95]
Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, A. Braun: Measuring the Complexity of Polygonal Objects. ACM-GIS 1995: 109- CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BRI96]
Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Parallel Processing of Spatial Joins Using R-trees. ICDE 1996: 258-265 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GAE96]
Christos Faloutsos, Volker Gaede: Analysis of n-Dimensional Quadtrees using the Hausdorff Fractal Dimension. VLDB 1996: 40-50 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GÜN93]
Oliver Günther: Efficient Computation of Spatial Joins. ICDE 1993: 50-59 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HUA97a]
Yun-Wu Huang, Matthew C. Jones, Elke A. Rundensteiner: Improving Spatial Intersect Joins Using Symbolic Intersect Detection. SSD 1997: 165-177 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HUA97b]
Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner: Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations. VLDB 1997: 396-405 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[IBG96]
...
[MIN95]
Ming-Ling Lo, Chinya V. Ravishankar: Generating Seeded Trees from Data Sets. SSD 1995: 328-347 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MIN96]
Ming-Ling Lo, Chinya V. Ravishankar: Spatial Hash-Joins. SIGMOD Conference 1996: 247-258 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[PAT96]
Jignesh M. Patel, David J. DeWitt: Partition Based Spatial-Merge Join. SIGMOD Conference 1996: 259-270 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ROG86]
...
[SAI94]
...
[SAM90]
Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SQL95]
...
[VEE95]
Hein M. Veenhof, Peter M. G. Apers, Maurice A. W. Houtsma: Optimisation of Spatial Joins Using Filters. BNCOD 1995: 136-154 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ZIM97]
...

Copyright © Tue Mar 16 02:22:07 2010 by Michael Ley (ley@uni-trier.de)