Multi-Step Processing of Spatial Joins.
Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger:
Multi-Step Processing of Spatial Joins.
SIGMOD Conference 1994: 197-208@inproceedings{DBLP:conf/sigmod/BrinkhoffKSS94,
author = {Thomas Brinkhoff and
Hans-Peter Kriegel and
Ralf Schneider and
Bernhard Seeger},
editor = {Richard T. Snodgrass and
Marianne Winslett},
title = {Multi-Step Processing of Spatial Joins},
booktitle = {Proceedings of the 1994 ACM SIGMOD International Conference on
Management of Data, Minneapolis, Minnesota, May 24-27, 1994},
publisher = {ACM Press},
year = {1994},
pages = {197-208},
ee = {http://doi.acm.org/10.1145/191839.191880, db/conf/sigmod/BrinkhoffKSS94.html},
crossref = {DBLP:conf/sigmod/94},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
Spatial joins are one of the most important operations for combining
spatial objects of several relations. In this paper, spatial join processing
is studied in detail for extended spatial objects in two-dimensional data
space. We present an approach for spatial join processing that is based
on three steps. First, a spatial join is performed on the minimum bounding
rectangles of the objects returning a set of candidates. Various approaches
for accelerating this step of join processing have been examined
at the last year's conference. In this paper, we focus on
the problem how to compute the answers from the set of candidates
which is handled by the following two steps. First of all, sophisticated
approximations are used to identify answers as well as to filter out false
hits from the set of candidates. For this purpose, we investigate various
types of conservative and progressive approximations. In the last step,
the exact geometry of the remaining candidates has to be tested against
the join predicate. The time required for computing spatial join predicates
can essentially be reduced when objects are adequately organized
in main memory. In our approach, objects are first decomposed into
simple components which are exclusively organized by a main-memory
resident spatial data structure. Overall, we present a complete approach
of spatial join processing on complex spatial objects. The performance
of the individual steps of our approach is evaluated with data sets from
real cartographic applications. The results show that our approach reduces
the total execution time of the spatial join by factors.
Copyright © 1994 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.
Online Version (ACM WWW Account required): Full Text in PDF Format
CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
BibTeX
Printed Edition
Richard T. Snodgrass, Marianne Winslett (Eds.):
Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, Minneapolis, Minnesota, May 24-27, 1994.
ACM Press 1994 BibTeX
,
SIGMOD Record 23(2),
June 1994
Contents
[Abstract and Index Terms]
[Full Text in PDF Format, 1682 KB]
References
- [AA 83]
- Tetsuo Asano, Takao Asano:
Minimum Partition of Polygonal Regions into Trapezoids.
FOCS 1983: 233-241 BibTeX
- [BG 90]
- Gabriele Blankenagel, Ralf Hartmut Güting:
Internal and External Algorithms for the Points-in-Regions Problem-the INSIDE Join of Geo-Relational Algebra.
Algorithmica 5(2): 251-276(1990) BibTeX
- [BHKS 93]
- Thomas Brinkhoff, Holger Horn, Hans-Peter Kriegel, Ralf Schneider:
A Storage and Access Architecture for Efficient Query Processing in Spatial Database Systems.
SSD 1993: 357-376 BibTeX
- [BK 94]
- ...
- [BKS 93a]
- Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger:
Efficient Processing of Spatial Joins Using R-Trees.
SIGMOD Conference 1993: 237-246 BibTeX
- [BKS 93b]
- 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 BibTeX
- [BKSS 90]
- 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
- [BZ 91]
- Dan Benson, Greg Zick:
Symbolic and Spatial Database for Structural Biology.
OOPSLA 1991: 329-339 BibTeX
- [DB 83]
- ...
- [Fal 88]
- Christos Faloutsos:
Gray Codes for Partial Match and Range Queries.
IEEE Trans. Software Eng. 14(10): 1381-1393(1988) BibTeX
- [Gün 89]
- Oliver Günther:
The Design of the Cell Tree: An Object-Oriented Index Structure for Geometric Databases.
ICDE 1989: 598-605 BibTeX
- [Gün 93]
- Oliver Günther:
Efficient Computation of Spatial Joins.
ICDE 1993: 50-59 BibTeX
- [Gut 84]
- Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57 BibTeX
- [Jag 90a]
- H. V. Jagadish:
Spatial Search with Polyhedra.
ICDE 1990: 311-319 BibTeX
- [Jag 90b]
- H. V. Jagadish:
Linear Clustering of Objects with Multiple Atributes.
SIGMOD Conference 1990: 332-342 BibTeX
- [KBS 93]
- Hans-Peter Kriegel, Thomas Brinkhoff, Ralf Schneider:
Efficient Spatial Query Processing in Geographic Database Systems.
IEEE Data Eng. Bull. 16(3): 10-15(1993) BibTeX
- [KHS 91]
- Hans-Peter Kriegel, Holger Horn, Michael Schiwietz:
The Performance of Object Decomposition Techniques for Spatial Query Processing.
SSD 1991: 257-276 BibTeX
- [ME 92]
- Priti Mishra, Margaret H. Eich:
Join Processing in Relational Databases.
ACM Comput. Surv. 24(1): 63-113(1992) BibTeX
- [Ore 86]
- Jack A. Orenstein:
Spatial Query Processing in an Object-Oriented Database System.
SIGMOD Conference 1986: 326-336 BibTeX
- [PS 85]
- ...
- [Sam 90]
- Hanan Samet:
The Design and Analysis of Spatial Data Structures.
Addison-Wesley 1990
BibTeX
- [SH76]
- Michael Ian Shamos, Dan Hoey:
Geometric Intersection Problems.
FOCS 1976: 208-215 BibTeX
- [SK 91]
- ...
- [SRF 87]
- Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos:
The R+-Tree: A Dynamic Index for Multi-Dimensional Objects.
VLDB 1987: 507-518 BibTeX
- [Wel 91]
- ...
Referenced by
- Hyoseop Shin, Bongki Moon, Sukho Lee:
Adaptive Multi-Stage Distance Join Processing.
SIGMOD Conference 2000: 343-354
- Christian S. Jensen:
Review - Multi-Step Processing of Spatial Joins.
ACM SIGMOD Digital Review 1: (1999)
- Weidong Chen, Jyh-Herng Chow, You-Chin Fuh, Jean Grandbois, Michelle Jou, Nelson Mendonça Mattos, Brian T. Tran, Yun Wang:
High Level Indexing of User-Defined Types.
VLDB 1999: 554-564
- Miyeon Kim, Sumi Lim, Jangsu Kim:
Development of Multi-step Filtering Processor.
DASFAA 1999: 169-176
- Gunter Saake, Andreas Heuer:
Datenbanken: Implementierungstechniken.
MITP-Verlag 1999, ISBN 3-8266-0513-6
Contents - Volker Gaede, Oliver Günther:
Multidimensional Access Methods.
ACM Comput. Surv. 30(2): 170-231(1998)
- Geraldo Zimbrao, Jano Moreira de Souza:
A Raster Approximation For Processing of Spatial Joins.
VLDB 1998: 558-569
- Roger Weber, Hans-Jörg Schek, Stephen Blott:
A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces.
VLDB 1998: 194-205
- Dimitris Papadias, Nikos Mamoulis, Vasilis Delis:
Algorithms for Querying by Spatial Structure.
VLDB 1998: 546-557
- Gísli R. Hjaltason, Hanan Samet:
Incremental Distance Join Algorithms for Spatial Databases.
SIGMOD Conference 1998: 237-248
- Yannis Theodoridis, Emmanuel Stefanakis, Timos K. Sellis:
Cost Models for Join Queries in Spatial Databases.
ICDE 1998: 476-483
- Hiroyuki Horinokuchi, Botao Wang, Susumu Kuroki, Akifumi Makinouchi:
A Spatiotemporal Query Processor Based on Simplicial Representation.
ER Workshops 1998: 520-531
- Euripides G. M. Petrakis, Christos Faloutsos:
Similarity Searching in Medical Image Databases.
IEEE Trans. Knowl. Data Eng. 9(3): 435-447(1997)
- Thomas Seidl, Hans-Peter Kriegel:
Efficient User-Adaptable Similarity Search in Large Multimedia Databases.
VLDB 1997: 506-515
- Nick Koudas, Kenneth C. Sevcik:
Size Separation Spatial Join.
SIGMOD Conference 1997: 324-335
- Norio Katayama, Shin'ichi Satoh:
The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries.
SIGMOD Conference 1997: 369-380
- Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner:
Integrated Query Processing Strategies for Spatial Path Queries.
ICDE 1997: 477-486
- Esa Falkenroth:
Computational Indexes for Time Series.
SSDBM 1996: 242-251
- Jignesh M. Patel, David J. DeWitt:
Partition Based Spatial-Merge Join.
SIGMOD Conference 1996: 259-270
- Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger:
Parallel Processing of Spatial Joins Using R-trees.
ICDE 1996: 258-265
- Peter A. Boncz, Wilko Quak, Martin L. Kersten:
Monet And Its Geographic Extensions: A Novel Approach to High Performance GIS Processing.
EDBT 1996: 147-166
- Christos Faloutsos:
Fast Searching by Content in Multimedia Databases.
IEEE Data Eng. Bull. 18(4): 31-40(1995)
- Erik G. Hoel, Hanan Samet:
Benchmarking Spatial Join Operations with Spatial Output.
VLDB 1995: 606-618
- Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer:
Generalized Search Trees for Database Systems.
VLDB 1995: 562-573
- Dimitris Papadias, Yannis Theodoridis, Timos K. Sellis, Max J. Egenhofer:
Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees.
SIGMOD Conference 1995: 92-103
- Christos Faloutsos, King-Ip Lin:
FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets.
SIGMOD Conference 1995: 163-174
- Jean-Pierre Cheiney, Vincent Oria:
Spatial Database Querying with Logic Languages.
DASFAA 1995: 342-349
- M. G. Martynov:
Spatial Joins and R-trees.
ADBIS 1995: 295-304
- Ralf Hartmut Güting:
An Introduction to Spatial Database Systems.
VLDB J. 3(4): 357-399(1994)
- Thomas Brinkhoff, Hans-Peter Kriegel:
The Impact of Global Clustering on Spatial Database Systems.
VLDB 1994: 168-179
- Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger:
GENESYS: A System for Efficient Spatial Query Processing.
SIGMOD Conference 1994: 519
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:20 2009