Partition Based Spatial-Merge Join.
Jignesh M. Patel, David J. DeWitt:
Partition Based Spatial-Merge Join.
SIGMOD Conference 1996: 259-270@inproceedings{DBLP:conf/sigmod/PatelD96,
author = {Jignesh M. Patel and
David J. DeWitt},
editor = {H. V. Jagadish and
Inderpal Singh Mumick},
title = {Partition Based Spatial-Merge Join},
booktitle = {Proceedings of the 1996 ACM SIGMOD International Conference on
Management of Data, Montreal, Quebec, Canada, June 4-6, 1996},
publisher = {ACM Press},
year = {1996},
pages = {259-270},
ee = {http://doi.acm.org/10.1145/233269.233338, db/conf/sigmod/PatelD96.html},
crossref = {DBLP:conf/sigmod/96},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
This paper describes PBSM (Partition Based Spatial-Merge), a new
algorithm for performing spatial join operation.
This algorithm is especially effective when neither of the inputs to
the join have an index on the joining attribute.
Such a situation could arise if both inputs to the join are
intermediate results in a complex query, or in a parallel environment
where the inputs must be dynamically redistributed.
The PBSM algorithm partitions the inputs into manageable chunks,
and joins them using a computational geometry based plane-sweeping
technique. This paper also presents a performance study comparing the
traditional indexed nested loops join algorithm, a spatial join algorithm
based on joining spatial indices, and the PBSM algorithm.
These comparisons are based on complete implementations of these
algorithms in Paradise, a database system for handling GIS applications.
Using real data sets, the performance study examines the behavior of these
spatial join algorithms in a variety of situations, including the cases
when both, one, or none of the inputs to the join have an suitable index.
The study also examines the effect of clustering the join inputs on the
performance of these join algorithms. The performance comparisons
demonstrates the feasibility, and applicability of the PBSM algorithm.
Copyright © 1996 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
H. V. Jagadish, Inderpal Singh Mumick (Eds.):
Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Quebec, Canada, June 4-6, 1996.
ACM Press 1996 BibTeX
,
SIGMOD Record 25(2),
June 1996
Contents
[Index Terms]
[Full Text in PDF Format, 1494 KB]
References
- [Arc95]
- ...
- [Ben75]
- Jon Louis Bentley:
Multidimensional Binary Search Trees Used for Associative Searching.
Commun. ACM 18(9): 509-517(1975) BibTeX
- [Ben79]
- Jon Louis Bentley:
Multidimensional Binary Search Trees in Database Applications.
IEEE Trans. Software Eng. 5(4): 333-340(1979) BibTeX
- [BHF93]
- Ludger Becker, Klaus Hinrichs, Ulrich Finke:
A New Algorithm for Computing Joins with Grid Files.
ICDE 1993: 190-197 BibTeX
- [BKS93]
- Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger:
Efficient Processing of Spatial Joins Using R-Trees.
SIGMOD Conference 1993: 237-246 BibTeX
- [BKSS90]
- 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
- [BKSS94]
- Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger:
Multi-Step Processing of Spatial Joins.
SIGMOD Conference 1994: 197-208 BibTeX
- [Bur86]
- ...
- [CDF+94]
- Michael J. Carey, David J. DeWitt, Michael J. Franklin, Nancy E. Hall, Mark L. McAuliffe, Jeffrey F. Naughton, Daniel T. Schuh, Marvin H. Solomon, C. K. Tan, Odysseas G. Tsatalos, Seth J. White, Michael J. Zwilling:
Shoring Up Persistent Applications.
SIGMOD Conference 1994: 383-394 BibTeX
- [CFR87]
- Christos Faloutsos, Timos K. Sellis, Nick Roussopoulos:
Analysis of Object Oriented Spatial Access Methods.
SIGMOD Conference 1987: 426-439 BibTeX
- [Cor95]
- ...
- [DKL+94]
- David J. DeWitt, Navin Kabra, Jun Luo, Jignesh M. Patel, Jie-Bing Yu:
Client-Server Paradise.
VLDB 1994: 558-569 BibTeX
- [DLPY93]
- ...
- [DNSS92]
- David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider, S. Seshadri:
Practical Skew Handling in Parallel Joins.
VLDB 1992: 27-40 BibTeX
- [GS87]
- ...
- [Gün93]
- Oliver Günther:
Efficient Computation of Spatial Joins.
ICDE 1993: 50-59 BibTeX
- [Gut84]
- Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57 BibTeX
- [HNKT90]
- Lilian Harada, Miyuki Nakano, Masaru Kitsuregawa, Mikio Takagi:
Query Processing for Multi-Attribute Clustered Records.
VLDB 1990: 59-70 BibTeX
- [HS95]
- Erik G. Hoel, Hanan Samet:
Benchmarking Spatial Join Operations with Spatial Output.
VLDB 1995: 606-618 BibTeX
- [KHT89]
- Masaru Kitsuregawa, Lilian Harada, Mikio Takagi:
Join Strategies on KB-Tree Indexed Relations.
ICDE 1989: 85-93 BibTeX
- [LR94]
- Ming-Ling Lo, Chinya V. Ravishankar:
Spatial Joins Using Seeded Trees.
SIGMOD Conference 1994: 209-220 BibTeX
- [LR95]
- Ming-Ling Lo, Chinya V. Ravishankar:
Generating Seeded Trees from Data Sets.
SSD 1995: 328-347 BibTeX
- [LR96]
- Ming-Ling Lo, Chinya V. Ravishankar:
Spatial Hash-Joins.
SIGMOD Conference 1996: 247-258 BibTeX
- [MC80]
- ...
- [MGR91]
- ...
- [NHS84]
- Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik:
The Grid File: An Adaptable, Symmetric Multikey File Structure.
ACM Trans. Database Syst. 9(1): 38-71(1984) BibTeX
- [NS86]
- ...
- [OM84]
- Jack A. Orenstein, T. H. Merrett:
A Class of Data Structures for Associative Searching.
PODS 1984: 181-190 BibTeX
- [OM88]
- Jack A. Orenstein, Frank Manola:
PROBE Spatial Data Modeling and Query Processing in an Image Database Application.
IEEE Trans. Software Eng. 14(5): 611-629(1988) BibTeX
- [Ore86]
- Jack A. Orenstein:
Spatial Query Processing in an Object-Oriented Database System.
SIGMOD Conference 1986: 326-336 BibTeX
- [Ore89]
- Jack A. Orenstein:
Redundancy in Spatial Databases.
SIGMOD Conference 1989: 295-305 BibTeX
- [Ore90]
- Jack A. Orenstein:
A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces.
SIGMOD Conference 1990: 343-352 BibTeX
- [PD]
- ...
- [PS88]
- ...
- [Rot91]
- Doron Rotem:
Spatial Join Indices.
ICDE 1991: 500-509 BibTeX
- [SFGM93]
- Michael Stonebraker, James Frew, Kenn Gardels, Jeff Meredith:
The Sequoia 2000 Benchmark.
SIGMOD Conference 1993: 2-11 BibTeX
- [Sto86]
- Michael Stonebraker:
The Case for Shared Nothing.
IEEE Database Eng. Bull. 9(1): 4-9(1986) BibTeX
- [Tig]
- ...
- [TY95]
- Kian-Lee Tan, Jeffrey Xu Yu:
A Performance Study of Declustering Strategies for Parallel Spatial Databases.
DEXA 1995: 157-166 BibTeX
- [Ube94]
- Michael Ubell:
The Montage Extensible DataBlade Achitecture.
SIGMOD Conference 1994: 482 BibTeX
- [Val87]
- Patrick Valduriez:
Join Indices.
ACM Trans. Database Syst. 12(2): 218-246(1987) BibTeX
- [ZG90]
- Hansjörg Zeller, Jim Gray:
An Adaptive Hash Join Algorithm for Multiuser Environments.
VLDB 1990: 186-197 BibTeX
Referenced by
- Hyoseop Shin, Bongki Moon, Sukho Lee:
Adaptive Multi-Stage Distance Join Processing.
SIGMOD Conference 2000: 343-354
- Christos Faloutsos, Bernhard Seeger, Agma J. M. Traina, Caetano Traina Jr.:
Spatial Join Selectivity Using Power Laws.
SIGMOD Conference 2000: 177-188
- Jochen Van den Bercken, Martin Schneider, Bernhard Seeger:
Plug&Join: An easy-to-use Generic Algorithm for Efficiently Processing Equi and Non-Equi Joins.
EDBT 2000: 495-509
- Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jan Vahrenhold, Jeffrey Scott Vitter:
A Unified Approach for Indexed and Non-Indexed Spatial Joins.
EDBT 2000: 413-429
- Michael Jaedicke, Bernhard Mitschang:
User-Defined Table Operators: Enhancing Extensibility for ORDBMS.
VLDB 1999: 494-505
- Nikos Mamoulis, Dimitris Papadias:
Integration of Spatial Join Algorithms for Processing Multiple Inputs.
SIGMOD Conference 1999: 1-12
- Hongjun Zhu, Jianwen Su, Oscar H. Ibarra:
An Index Structure for Spatial Joins in Linear Constraint Databases.
ICDE 1999: 636-643
- Geraldo Zimbrao, Jano Moreira de Souza:
A Raster Approximation For Processing of Spatial Joins.
VLDB 1998: 558-569
- Narayanan Shivakumar, Hector Garcia-Molina, Chandra Chekuri:
Filtering with Approximate Predicates.
VLDB 1998: 263-274
- Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter:
Scalable Sweeping-Based Spatial Join.
VLDB 1998: 570-581
- Oliver Günther, Vincent Oria, Philippe Picouet, Jean-Marc Saglio, Michel Scholl:
Benchmarking Spatial Joins À La Carte.
SSDBM 1998: 32-41
- Jeffrey Scott Vitter:
External Memory Algorithms.
PODS 1998: 119-128
- Yannis Theodoridis, Emmanuel Stefanakis, Timos K. Sellis:
Cost Models for Join Queries in Spatial Databases.
ICDE 1998: 476-483
- Nick Koudas, Kenneth C. Sevcik:
High Dimensional Similarity Joins: Algorithms and Performance Evaluation.
ICDE 1998: 466-475
- John C. Shafer, Rakesh Agrawal:
Parallel Algorithms for High-dimensional Similarity Joins for Data Mining Applications.
VLDB 1997: 176-185
- Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner:
Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations.
VLDB 1997: 396-405
- Sven Helmer, Guido Moerkotte:
Evaluation of Main Memory Join Algorithms for Joins with Set Comparison Join Predicates.
VLDB 1997: 386-395
- Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner:
A Cost Model for Estimating the Performance of Spatial Joins Using R-trees.
SSDBM 1997: 30-38
- Jignesh M. Patel, Jie-Bing Yu, Navin Kabra, Kristin Tufte, Biswadeep Nag, Josef Burger, Nancy E. Hall, Karthikeyan Ramasamy, Roger Lueder, Curt J. Ellmann, Jim Kupsch, Shelly Guo, David J. DeWitt, Jeffrey F. Naughton:
Building a Scaleable Geo-Spatial DBMS: Technology, Implementation, and Evaluation.
SIGMOD Conference 1997: 336-347
- Nick Koudas, Kenneth C. Sevcik:
Size Separation Spatial Join.
SIGMOD Conference 1997: 324-335
- Kyuseok Shim, Ramakrishnan Srikant, Rakesh Agrawal:
High-Dimensional Similarity Joins.
ICDE 1997: 301-311
- Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner:
Integrated Query Processing Strategies for Spatial Path Queries.
ICDE 1997: 477-486
- Ming-Ling Lo, Chinya V. Ravishankar:
Spatial Hash-Joins.
SIGMOD Conference 1996: 247-258
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:32 2009
