Edwin H. Jacox
Hanan Samet
Skip Abstract Section
Skip Supplemental Material SectionAbstract
A variety of techniques for performing a spatial join are reviewed. Instead of just summarizing the literature and presenting each technique in its entirety, distinct components of the different techniques are described and each is decomposed into an overall framework for performing a spatial join. A typical spatial join technique consists of the following components: partitioning the data, performing internal-memory spatial joins on subsets of the data, and checking if the full polygons intersect. Each technique is decomposed into these components and each component addressed in a separate section so as to compare and contrast similar aspects of each technique. The goal of this survey is to describe the algorithms within each component in detail, comparing and contrasting competing methods, thereby enabling further analysis and experimentation with each component and allowing the best algorithms for a particular situation to be built piecemeal, or, even better, enabling an optimizer to choose which algorithms to use.
Supplemental Material
Available for Download
pdf
p1-jacox-apndx.pdf (1.7 MB)
Online appendix to designing mediation for context-aware applications. The appendix supports the information on page 1.
- Abel, D. J., Gaede, V., Power, R., and Zhou, X. 1999. Caching strategies for spatial joins. GeoInformatica 3, 1 (Jun.), 33--59.]] Google Scholar
Digital Library
- Abel, D. J., Ooi, B. C., Tan, K.-L., Power, R., and Yu, J. X. 1995. Spatial join strategies in distributed spatial DBMS. In Advances in Spatial Databases---4th International Symposium (SSD) (Portland, ME), M. J. Egenhofer and J. R. Herring, Eds. Lecture Notes in Computer Science, vol. 1619, Springer Verlag. 348--367.]] Google ScholarDigital Library
- An, N., Yang, Z.-Y., and Sivasubramaniam, A. 2001. Selectivity estimation for spatial joins. In Proceedings of the 17th IEEE International Conference on Data Engineering (Heidelberg, Germany). 368--375.]] Google ScholarDigital Library
- Aref, W. G. and Samet, H. 1994a. A cost model for query optimization using R-trees. In Proceedings of the 2nd ACM Workshop on Geographic Information Systems (Gaithersburg, MD), N. Pissinou and K. Makki, Eds. 60--67.]]Google Scholar
- Aref, W. G. and Samet, H. 1994b. Hashing by proximity to process duplicates in spatial databases. In Proceedings of the 3rd International Conference on Information and Knowledge Management (CIKM) (Gaithersburg, MD). 347--354.]] Google ScholarDigital Library
- Aref, W. G. and Samet, H. 1994c. The spatial filter revisited. In Proceedings of the 6th International Symposium on Spatial Data Handling (Edinburgh, Scotland), T. C. Waugh and R. G. Healey, Eds. 190--208.]]Google Scholar
- Aref, W. G. and Samet, H. 1996. Cascaded spatial join algorithms with spatially sorted output. In Proceedings of the 4th ACM Workshop on Geographic Information Systems (Gaithersburg, MD), S. Shekhar and P. Bergougnoux, Eds. 17--24.]] Google ScholarDigital Library
- Arge, L., Hinrichs, K. H. Vahrenhold, J., and Vitter, J. S. 1999. Efficient bulk operations on dynamic R-trees. In Proceedings of the 1st Workshop on Algorithm Engineering and Experimentation (ALENEX) (Baltimore, MD), M. T. Goodrich and C. C. McGeoch, Eds. Lecture Notes in Computer Science, vol. 1619. Springer Verlag. 328--348.]] Google ScholarDigital Library
- Arge, L., Procopiuc, O., Ramaswamy, S., Suel, T., Vahrenhold, J., and Vitter, J. S. 2000. A unified approach for indexed and non-indexed spatial joins. In Proceedings of the 7th International Conference on Extending Database Technology (EDBT) (Konstanz, Germany), C. Zaniolo et al. Lecture Notes in Computer Science, vol. 1777. Springer Verlag. 413--429.]] Google ScholarDigital Library
- Arge, L., Procopiuc, O., Ramaswamy, S., Suel, T., and Vitter, J. S. 1998. Scalable sweeping-based spatial join. In Proceedings of the 24th International Conference on Very Large Data Bases (VLDB) (New York), A. Gupta et al. Eds. 570--581.]] Google ScholarDigital Library
- Badawy, W. M. and Aref, W. G. 1999. On local heuristics to speed up polygon-polygon intersection tests. In Proceedings of the 7th ACM International Symposium on Advances in Geographic Information Systems (Kansas City, MO), C. B. Medeiros, Eds. 97--102.]] Google ScholarDigital Library
- Balaban, I. J. 1995. An optimal algorithm for finding segments intersections. In SCG: Proceedings of the 11th Annual Symposium on Computational Geometry (Vancouver, BC). 211--219.]] Google ScholarDigital Library
- Becker, L., Hinrichs, K., and Finke, U. 1993. A new algorithm for computing joins with grid files. In Proceedings of the 9th IEEE International Conference on Data Engineering (Vienna, Austria). 190--197.]] Google ScholarDigital Library
- Belussi, A., Bertino, E., and Nucita, A. 2004. Grid based methods for estimating spatial join selectivity. In Proceedings of the 12th ACM International Workshop on Advances in Geographic Information Systems (Washington, DC), I. F. Cruz and D. Pfoser, Eds. 92--100.]] Google ScholarDigital Library
- Belussi, A. and Faloutsos, C. 1995. Estimating the selectivity of spatial queries using the ‘correlation’ fractal dimension. In Proceedings of the 21st International Conference on Very Large Data Bases (VLDB) (Zurich, Switzerland), U. Dayal et al. Eds. 299--310.]] Google ScholarDigital Library
- Bentley, J. L. 1975. Multidimensional binary search trees used for associative searching. Commun. ACM 18, 9 (Sept.), 509--517.]] Google ScholarDigital Library
- Brinkhoff, T. and Kriegel, H.-P. 1994a. Approximations for a multi-step processing of spatial joins. In IGIS: International Workshop on Advanced Research in Geographic Information Systems (Monte Verità, Ascona, Switzerland), J. Nievergelt et al. Eds. 25--34.]] Google ScholarDigital Library
- Brinkhoff, T. and Kriegel, H.-P. 1994b. The impact of global clustering on spatial database systems. In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB) (Santiago, Chile), J. Bocca et al. Eds.]] Google ScholarDigital Library
- Brinkhoff, T., Kriegel, H.-P., and Schneider, R. 1993. Comparison of approximations of complex objects used for approximation-based query processing in spatial database systems. In Proceedings of the 9th IEEE International Conference on Data Engineering (Vienna, Austria). 40--49.]] Google ScholarDigital Library
- Brinkhoff, T., Kriegel, H.-P., Schneider, R., and Seeger, B. 1994. Multi-Step processing of spatial joins. In Proceedings of the ACM SIGMOD Conference (Minneapolis, MN). 197--208.]] Google ScholarDigital Library
- Brinkhoff, T., Kriegel, H.-P., and Seeger, B. 1993. Efficient processing of spatial joins using R-trees. In Proceedings of the ACM SIGMOD Conference (Washington, DC). 237--246.]] Google ScholarDigital Library
- Brinkhoff, T., Kriegel, H.-P., and Seeger, B. 1996. Parallel processing of spatial joins using R-trees. In Proceedings of the 12th International Conference on Data Engineering (New Orleans, LA), S. Y. W. Su, Ed. 258--265.]] Google ScholarDigital Library
- Brinkmann, A. and Hinrichs, K. 1998. Implementing exact line segment intersection in map overlay. In Proceedings of the 8th International Symposium on Spatial Data Handling (Burnaby, BC), S. Y. W. Su, Ed. 569--579.]]Google Scholar
- Chazelle, B. and Edelsbrunner, H. 1992. An optimal algorithm for intersecting line segments in the plane. J. ACM 39, 1 (Jan.), 1--54.]] Google ScholarDigital Library
- Chiba, N. and Nishizeki, T. 1989. The Hamiltonian cycle problem is linear-time solvable for 4-connect planar graphs. J. Algorithms 10, 2 (June), 187--211.]] Google ScholarDigital Library
- Cormen, T. H., Leiserson, C. E., and Rivest, R. L. 1990. Introduction to Algorithms. MIT Press/McGraw-Hill, Cambridge, MA. 173--174.]] Google ScholarDigital Library
- Corral, A., Vassilakopoulos, M., and Manolopoulos, Y. 1999. Algorithms for joining R-trees and linear region quadtrees. In Advances in Spatial Databases---6th International Symposium, (SSD) (Hong Kong, China), R. H. Güting et al. Eds. Lecture Notes in Computer Science, vol. 1651, Springer Verlag. 251--269.]] Google ScholarDigital Library
- Das, A., Gehrke, J., and Riedewald, M. 2004. Approximation techniques for spatial data. In Proceedings of the ACM SIGMOD Conference (Paris). 695--706.]] Google ScholarDigital Library
- Dillencourt, M. B. and Samet, H. 1996. Using topological sweep to extract the boundaries of regions in maps represented by region quadtrees. Algorithmica 15, 1 (Jan.), 82--102.]]Google ScholarDigital Library
- Dittrich, J.-P. and Seeger, B. 2000. Data redundancy and duplicate detection in spatial join processing. In Proceedings of the 16th IEEE International Conference on Data Engineering (San Diego, CA). 535--546.]] Google ScholarDigital Library
- Edelsbrunner, H. 1983. A new approach to rectangle intersections: Part I. Int. J. Comput. Math. 13, 3--4, 209--219.]]Google Scholar
- Elmasri, R. and Navathe, S. B. 2000. Fundamentals of Database Systems, 3rd Ed. Addison-Wesley, Reading, MA.]] Google ScholarDigital Library
- Enderle, J., Hampel, M., and Seidl, T. 2004. Joining interval data in relational databases. In Proceedings of the ACM SIGMOD Conference (Paris, France). 683--694.]] Google ScholarDigital Library
- Faloutsos, C. and Kamel, I. 1994. Beyond uniformity and independence: analysis of R-trees using the concept of fractal dimension. In Proceedings of the 13th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) (Minneapolis, MN). 4--13.]] Google ScholarDigital Library
- Faloutsos, C., Seeger, B., Traina, A. J. M., and Traina Jr., C. 2000. Spatial join selectivity using power laws. In Proceedings of the ACM SIGMOD Conference (Dallas, TX), W. Chen et al. Eds. 177--188.]] Google ScholarDigital Library
- Finkel, R. A. and Bentley, J. L. 1974. Quad trees: A data structure for retrieval on composite keys. Acta Informatica 4, 1, 1--9.]]Google ScholarDigital Library
- Fotouhi, F. and Pramanik, S. 1989. Optimal secondary storage access sequence for performing relational join. IEEE Trans. Knowl. Data Eng. 1, 3 (Sept.), 318--328.]] Google ScholarDigital Library
- Gaede, V. 1995. Optimal redundancy in spatial database systems. In Advances in Spatial Databases---4th International Symposium (SSD) (Portland, ME), M. J. Egenhofer and J. R. Herring, Eds. Lecture Notes in Computer Science, vol. 951, Springer Verlag. 96--116.]] Google ScholarDigital Library
- Gaede, V. and Günther, O. 1998. Multidimensional access methods. ACM Comput. Surv. 20, 2 (Jun.), 170--231.]] Google ScholarDigital Library
- Garcia-Molina, H., Ullman, J. D., and Widom, J. 2000. Database System Implementation. Prentice Hall, Englewood Cliffs, NJ.]] Google ScholarDigital Library
- Gottschalk, S., Lin, M. C., and Manocha, D. 1996. OBBTree: A hierarchical structure for rapid interference detection. In Proceedings of the SIGGRAPH Conference (New Orleans, LA). 171--180.]] Google ScholarDigital Library
- Graefe, G. 1993. Query evaluation techniques for large databases. ACM Comput. Surv. 25, 2 (Jun.), 73--170.]] Google ScholarDigital Library
- Günther, O. 1993. Efficient computation of spatial joins. In Proceedings of the 9th IEEE International Conference on Data Engineering (Vienna, Austria). 50--59.]] Google ScholarDigital Library
- Günther, O., Oria, V., Picouet, P., Saglio, J.-M., and Scholl, M. 1998. Benchmarking spatial joins à la carte. In Proceedings of the 10th International Conference on Scientific and Statistical Database Management (Capri, Italy), M. Rafanelli and M. Jarke, Eds. 32--41.]] Google ScholarDigital Library
- Gurret, C. and Rigaux, P. 2000. The sort/sweep algorithm: A new method for R-tree based spatial joins. In Proceedings of the 12th International Conference on Statistical and Scientific Database Management (SSDBM) (Berlin, Germany). 153--165.]] Google ScholarDigital Library
- Güting, R. H. and Schilling, W. 1987. A practical divide-and-conquer algorithm for the rectangle intersection problem. Inf. Sci. 42, 2 (Jul.), 95--112.]] Google ScholarDigital Library
- Guttman, A. 1984. R-trees: A dynamic index structure for spatial searching. In Proceedings of the ACM SIGMOD Conference (Boston, MA). 47--57.]] Google ScholarDigital Library
- Hanson, E. N. 1991. The interval skip list: A data structure for finding all intervals that overlap a point. Tech. Rep. WSU--CS--91--01, Department of Computer Science and Engineering Wright State University, Dayton, OH.]]Google Scholar
- Harada, L., Nakano, M., Kitsuregawa, M., and Takagi, M. 1990. Query processing for multi-attribute clustered records. In 16th International Conference on Very Large Data Bases (Brisbane, Queensland, Australia), D. McLeod et al. Eds. 59--70.]] Google ScholarDigital Library
- Hellerstein, J. M., Naughton, J. F., and Pfeffer, A. 1995. Generalized search trees for database systems. In Proceedings of the 21st International Conference on Very Large Data Bases (VLDB) (Zurich, Switzerland), U. Dayal et al. Eds. 562--573.]] Google ScholarDigital Library
- Hjaltason, G. R. and Samet, H. 1999. Improved bulk-loading algorithms for quadtrees. In Proceedings of the 7th ACM International Symposium on Advances in Geographic Information Systems. (Kansas City, MO), C. B. Medeiros, Ed. 110--115.]] Google ScholarDigital Library
- Hoel, E. and Samet, H. 1994. Data-Parallel spatial join algorithms. In Proceedings of the 23rd International Conference on Parallel Processing (St. Charles, IL), vol. 3. 227--234.]] Google ScholarDigital Library
- Hoel, E. G. and Samet, H. 1995. Benchmarking spatial join operations with spatial output. In Proceedings of the 21st International Conference on Very Large Data Bases (VLDB) (Zurich, Switzerland), U. Dayal et al. Eds. 606--618.]] Google ScholarDigital Library
- Huang, Y.-W., Jing, N., and Rundensteiner, E. A. 1997a. A cost model for estimating the performance of spatial joins using R-trees. In Proceedings of the 9th International Conference on Scientific and Statistical Database Management (Olympia, WA), Y. E. Ioannidis and D. M. Hansen, Eds. 30--38.]] Google ScholarDigital Library
- Huang, Y.-W., Jing, N., and Rundensteiner, E. A. 1997b. Spatial joins using R-trees: Breadth-First traversal with global optimizations. In Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB) (Athens, Greece), M. Jarke et al. Eds. 396--405.]] Google ScholarDigital Library
- Jacox, E. and Samet, H. 2003. Iterative spatial join. ACM Trans. Database Syst. 28, 3 (Sept.), 268--294.]] Google ScholarDigital Library
- Kim, S.-W., Cho, W.-S., Lee, M.-J., and Whang, K.-Y. 1995. A new algorithm for processing joins using the multilevel grid file. In Proceedings of the 4th International Conference on Database Systems for Advanced Applications (DASFAA) (Singapore), T. W. Ling and Y. Masunaga, Eds. vol. 5. 115--123.]] Google ScholarDigital Library
- Kitsuregawa, M., Harada, L., and Takagi, M. 1989. Join strategies on KD-tree indexed relations. In Proceedings of the 5th IEEE International Conference on Data Engineering (Los Angeles, CA). 85--93.]] Google ScholarDigital Library
- Knuth, D. E. 1973. The Art of Computer Programming: Sorting and Searching, vol. 3. Addison-Wesley, Reading, MA.]]Google Scholar
- Koudas, N. and Sevcik, K. C. 1997. Size separation spatial join. In Proceedings of the ACM SIGMOD Conference (Tucson, AZ), J. Peckham, Ed. 324--335.]] Google ScholarDigital Library
- Koudas, N. and Sevcik, K. C. 1998. High dimensional similarity joins: Algorithms and performance evaluation. In Proceedings of the 14th IEEE International Conference on Data Engineering (Orlando, FL). 466--475.]] Google ScholarDigital Library
- Kumar, V. 1992. Algorithms for constraints satisfaction problems: A survey. AI Mag. 13, 1 (Spr.), 32--44.]] Google ScholarDigital Library
- Lo, M.-L. and Ravishankar, C. V. 1994. Spatial joins using seeded trees. In Proceedings of the ACM SIGMOD Conference (Minneapolis, MN). 209--220.]] Google ScholarDigital Library
- Lo, M.-L. and Ravishankar, C. V. 1995. Generating seeded trees from data sets. In Advances in Spatial Databases---4th International Symposium (SSD) (Portland, ME), M. J. Egenhofer and J. R. Herring, Eds. Lecture Notes in Computer Science, vol. 951, Springer Verlag. 328--347.]] Google ScholarDigital Library
- Lo, M.-L. and Ravishankar, C. V. 1996. Spatial hash-joins. In Proceedings of the ACM SIGMOD Conference (Montréal, Canada). 247--258.]] Google ScholarDigital Library
- Lu, H., Luo, R., and Ooi, B. C. 1995. Spatial joins by precomputation of approximations. In Proceedings of the 6th Australasian Database Conference (Glenelg, South Australia). 132--142.]]Google Scholar
- Luo, G., Naughton, J. F., and Ellmann, C. 2002. A non-blocking parallel spatial join algorithm. In Proceedings of the 18th International Conference on Data Engineering (San Jose, CA). 697--705.]] Google ScholarDigital Library
- Mairson, H. G. and Stolfi, J. 1988. Reporting and counting intersections between two sets of line segments. In Theoretical Foundations of Computer Graphics and CAD, R. A. Earnshaw, Ed. Springer Verlag, Berlin 307--325.]]Google Scholar
- Mamoulis, N., Kalnis, P., Bakiras, S., and Li, X. 2003. Optimization of spatial joins on mobile devices. In Advances in Spatial and Temporal Databases: 8th International Symposium (SSTD) (Santorini Island, Greece). 233--251.]]Google Scholar
- Mamoulis, N. and Papadias, D. 1999. Integration of spatial join algorithms for processing multiple inputs. In Proceedings of the ACM SIGMOD Conference (Philadelphia, PA). 1--12.]] Google ScholarDigital Library
- Mamoulis, N. and Papadias, D. 2001a. Multiway spatial joins. ACM Trans. Database Syst. 26, 4 (Dec.), 424--475.]] Google ScholarDigital Library
- Mamoulis, N. and Papadias, D. 2001b. Selectivity estimation of complex spatial queries. In Advances in Spatial and Temporal Databases: 7th International Symposium (SSTD) (Redondo Beach, CA). 155--174.]] Google ScholarDigital Library
- Mamoulis, N. and Papadias, D. 2003. Slot index spatial join. IEEE Trans. Knowl. Data Eng. 15, 1, 211--231.]] Google ScholarDigital Library
- Mamoullis, N. and Papadias, D. 1998. Constraint-Based algorithms for computing clique intersection joins. In Proceedings of the 6th ACM International Symposium on Advances in Geographic Information Systems (Washington, DC), R. Laurini et al. Eds. 118--123.]] Google ScholarDigital Library
- McCreight, E. M. 1985. Priority search trees. SIAM J. Comput. 14, 2 (May), 257--276.]]Google ScholarCross Ref
- Merrett, T. H., Kambayashi, Y., and Yasuura, H. 1981. Scheduling of page-fetches in join operations. In Very Large Data Bases, 7th International Conference (Cannes, France). 488--498.]]Google Scholar
- Mishra, P. and Eich, M. H. 1992. Join processing in relational databases. ACM Comput. Surv. 24, 1 (Mar.), 63--113.]] Google ScholarDigital Library
- Nelson, R. C. and Samet, H. 1987. A population analysis for hierarchical data structures. In Proceedings of the ACM SIGMOD Conference (San Francisco, CA). 270--277.]] Google ScholarDigital Library
- Neyer, G. and Widmayer, P. 1997. Singularities make spatial join scheduling hard. In Algorithms and Computation, 8th International Symposium, (ISAAC) (Singapore). 293--302.]] Google ScholarDigital Library
- Nievergelt, J., Hinterberger, H., and Sevcik, K. C. 1984. The grid file: An adaptable, symmetric multikey file structure. ACM Trans. Database Syst. 9, 1 (Mar.), 38--71.]] Google ScholarDigital Library
- Orenstein, J. A. 1986. Spatial query processing in an object-oriented database system. In Proceedings of the ACM SIGMOD Conference (Washington, DC). 326--336.]] Google ScholarDigital Library
- Orenstein, J. A. 1989a. Redundancy in spatial databases. In Proceedings of the ACM SIGMOD Conference (Portland, OR). 294--305.]] Google ScholarDigital Library
- Orenstein, J. A. 1989b. Strategies for optimizing the use of redundancy in spatial databases. In Design and Implementation of Large Spatial Databases---1st Symposium (SSD) (Santa Barbara, CA), A. Buchmann et al. Eds. Lecture Notes in Computer Science, vol. 409, Springer Verlag. 115--134.]] Google ScholarDigital Library
- Orenstein, J. A. and Manola, F. A. 1988. PROBE spatial data modeling and query processing in an image database application. IEEE Trans. Softw. Eng. 14, 5 (May), 611--629.]] Google ScholarDigital Library
- Ottmann, T. and Wood, D. 1986. Space-Economical plane-sweep algorithms. Comput. Vis. Graph. Image Proc. 34, 1 (Apr.), 35--51.]] Google ScholarDigital Library
- Ozsu, M. T. and Valduriez, P. 1999. Principles of Distributed Database Systems, 2nd Ed. Prentice-Hall, Englewood Cliffs, NJ.]] Google ScholarDigital Library
- Papadias, D. and Arkoumanis, D. 2002. Approximate processing of multiway spatial joins in very large databases. In Advances in Database Technology (EDBT) 8th International Conference on Extending Database Technology (Prague, Czech Republic), C. S. Jensen et al. Eds. Lecture Notes in Computer Science, vol. 2287, Springer Verlag. 179--196.]] Google ScholarDigital Library
- Papadias, D., Mamoulis, N., and Delis, V. 1998. Algorithms for querying by spatial structure. In Proceedings of the 24th International Conference on Very Large Data Bases (VLDB) (New York), A. Gupta et al. Eds. 546--557.]] Google ScholarDigital Library
- Papadias, D., Mamoulis, N., and Theodoridis, Y. 1999. Processing and optimization of multiway spatial joins using R-trees. In Proceedings of the 18th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) (Philadelphia, PA). 44--55.]] Google ScholarDigital Library
- Papadopoulos, A., Rigaux, P., and Scholl, M. 1999. A performance evaluation of spatial join processing strategies. In Advances in Spatial Databases---6th International Symposium. (SSD) (Hong Kong, China), R. H. Güting et al. Eds. Lecture Notes in Computer Science, vol. 1651, Springer Verlag. 286--307.]] Google ScholarDigital Library
- Park, H.-H., Cha, G.-H., and Chung, C.-W. 1999. Multi-Way spatial joins using R-trees: Methodology and performance evaluation. In Advances in Spatial Databases---6th International Symposium (SSD) (Hong Kong, China), R. H. Güting et al. Eds. Lecture Notes in Computer Science, vol. 1651, Springer Verlag. 229--250.]] Google ScholarDigital Library
- Park, H.-H., Lee, C.-G., Lee, Y.-J., and Chung, C.-W. 1999. Early separation of filter and refinement steps in spatial query optimization. In Proceedings of the 6th International Conference on Database Systems for Advanced Applications (DASFAA) (Hsinchu, Taiwan), A. L. P. Chen and F. H. Lochovsky, Eds. 161--168.]] Google ScholarDigital Library
- Patel, J. M. and DeWitt, D. J. 1996. Partition based spatial-merge join. In Proceedings of the ACM SIGMOD Conference (Montréal, Canada). 259--270.]] Google ScholarDigital Library
- Patel, J. M. and DeWitt, D. J. 2000. Clone join and shadow join: Two parallel spatial join algorithms. In Proceedings of the 8th ACM International Symposium on Advances in Geographic Information Systems (Washington, DC). 54--61.]] Google ScholarDigital Library
- Preparata, F. P. and Shamos, M. I. 1985. Computational Geometry: An Introduction. Springer Verlag, New York.]] Google ScholarDigital Library
- Pugh, W. 1990. Skip lists: A probabilistic alternative to balanced trees. Commun. ACM 33, 6 (Jun.), 668--676.]] Google ScholarDigital Library
- Rosenberg, J. B. 1985. Geographical data structures compared: A study of data structures supporting region queries. IEEE Trans. Comput.-Aided Des. 4, 1 (Jan.), 53--67.]]Google ScholarDigital Library
- Rotem, D. 1991. Spatial join indices. In Proceedings of the 7th IEEE International Conference on Data Engineering (Kobe, Japan). 500--509.]] Google ScholarDigital Library
- Samet, H. 1990. The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA.]] Google ScholarDigital Library
- Samet, H. 2006. Foundations of Multidimensional and Metric Data Structures. Morgan-Kaufmann, San Francisco.]] Google ScholarDigital Library
- Seeger, B. 1991. Performance comparison of segment access methods implemented on top of the buddy-tree. In Advances in Spatial Databases---2nd Symposium (SSD) (Zurich, Switzerland), O. Günther and H.-J. Schek, Eds. Lecture Notes in Computer Science, vol. 525, Springer Verlag. 277--296.]] Google ScholarDigital Library
- Song, J.-W., Whang, K.-Y., Lee, Y.-K., Lee, M.-J., and Kim, S.-W. 1999. Spatial join processing using corner transformation. IEEE Trans. Knowl. Data Eng. 11, 4 (Jul./Aug.), 688--695.]] Google ScholarDigital Library
- Sun, C., Agrawal, D., and Abbadi, A. E. 2003. Hardware acceleration for spatial selections and joins. In Proceedings of the ACM SIGMOD Conference (San Diego, CA). 455--466.]] Google ScholarDigital Library
- Tan, K.-L., Ooi, B. C., and Abel, D. J. 2000. Exploiting spatial indexes for semijoin-based join processing in distributed spatial databases. IEEE Trans. Knowl. Data Eng. 12, 6 (Nov./Dec.), 920--937.]] Google ScholarDigital Library
- Theodoridis, Y., Stefanakis, E., and Sellis, T. K. 1998. Cost models for join queries in spatial databases. In Proceedings of the 14th IEEE International Conference on Data Engineering (Orlando, FL). 476--483.]] Google ScholarDigital Library
- Ulrich, T. 2000. Loose octrees. In Game Programming Gems, M. A. DeLoura, Ed. Charles River Media, Rockland, MA. 444--453.]]Google Scholar
- van den Bercken, J., Seeger, B., and Widmayer, P. 1997. A generic approach to bulk loading multidimensional index structures. In Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB) (Athens, Greece), M. Jarke et al. Eds. 406--415.]] Google ScholarDigital Library
- van den Bercken, J., Seeger, B., and Widmayer, P. 1999. The bulk index join: A generic approach to processing non-equijoins. In Proceedings of the 15th International Conference on Data Engineering (Sydney, Austrialia). 257.]] Google ScholarDigital Library
- van Oosterom, P. 1994. An R-tree based map-overlay algorithm. In EGIS/MARI: 5th European Conference on Geographical Information Systems (Paris). 318--327.]]Google Scholar
- van Roessel, J. W. 1987. Design of a spatial data structure using the relational normal forms. Int. J. Geograph. Inf. Syst. 1, 1 (Jan.), 33--50.]]Google Scholar
- van Roessel, J. W. 1991. A new approach to plane-sweep overlay: Topological structuring and line-segment classification. Cartography Geograph. Inf. Syst. 18, 1 (Jan.), 49--67.]]Google Scholar
- van Roessel, J. W. 1994. An integrated point-attribute model for four types of areal GIS features. In Proceedings of the 6th International Symposium on Spatial Data Handling (Edinburgh, Scotland). 137--144.]]Google Scholar
- Veenhof, H. M., Apers, P. M. G., and Houtsma, M. A. W. 1995. Optimisation of spatial joins using filters. In Advances in Databases, Proceedings of 13th British National Conference on Databases (BNCOD) (Manchester, UK), C. A. Goble and J. A. Keane, Eds. Lecture Notes in Computer Science, vol. 940, Springer Verlag. 136--154.]] Google ScholarDigital Library
- Whang, K.-Y. 1991. The multilevel grid file---A dynamic hierarchical multidimensional file structure. In Proceedings of the 2nd International Conference on Database Systems for Advanced Applications (DASFAA) (Tokyo, Japan), A. Makinouchi, Ed. 449--459.]] Google ScholarDigital Library
- Zhou, X., Abel, D. J., and Truffet, D. 1997. Data partitioning for parallel spatial join processing. In Advances in Spatial Databases---5th International Symposium (SSD) (Berlin), M. Scholl and A. Voisard, Eds. Lecture Notes in Computer Science, vol. 1262, Springer Verlag. 178--196.]] Google ScholarDigital Library
- Zhu, H., Su, J., and Ibarra, O. H. 2000a. Extending rectangle join algorithms for rectilinear polygons. In Web-Age Information Management: 1st International Conference (WAIM) (Shanghai, China). 247--258.]] Google ScholarDigital Library
- Zhu, H., Su, J., and Ibarra, O. H. 2000b. Toward spatial joins for polygons. In Proceedings of the 12th International Conference on Statistical and Scientific Database Management (SSDBM) (Berlin). 233--241.]] Google ScholarDigital Library
- Zhu, H., Su, J., and Ibarra, O. H. 2001. On multi-way spatial joins with direction predicates. In Advances in Spatial and Temporal Databases: 7th International Symposium (SSTD) (Redondo Beach, CA). 217--235.]] Google ScholarDigital Library
- Zhu, M., Papadias, D., Zhang, J., and Lee, D. L. 2005. Top-k spatial joins. IEEE Trans. Knowl. Data Eng. 17, 4 (Apr.), 567--579.]] Google ScholarDigital Library
- Zimbrao, G. and de Souza, J. M. 1998. A Raster approximation for processing of spatial joins. In Proceedings of the 24th International Conference on Very Large Data Bases (VLDB) (New York), A. Gupta et al. Eds. 558--569.]] Google ScholarDigital Library
Index Terms
- Spatial join techniques
Recommendations
Iterative spatial join
The key issue in performing spatial joins is finding the pairs of intersecting rectangles. For unindexed data sets, this is usually resolved by partitioning the data and then performing a plane sweep on the individual partitions. The resulting join can ...
Query optimizer for spatial join operations
GIS '06: Proceedings of the 14th annual ACM international symposium on Advances in geographic information systemsThis paper presents a query optimizer module based on cost estimation that chooses the best filtering step algorithm to perform a specific spatial join operation. A set of expressions to predict the number of I/O operations and the response time of each ...
Clone join and shadow join: two parallel spatial join algorithms
GIS '00: Proceedings of the 8th ACM international symposium on Advances in geographic information systemsSpatial applications frequently need to join two data sets based on some spatial relationship between objects in the two data sets. This operation, called a spatial join, is an expensive operation and in the past many algorithms have been proposed for ...
Comments