Spatial join techniques

ABSTRACT

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.

REFERENCES

• 1: David J. Abel , Volker Gaede , Robert A. Power , Xiaofang Zhou, Caching Strategies for Spatial Joins, Geoinformatica, v.3 n.1, p.33-59, March 1999 [doi>10.1023/A:1009844729517]
• 2: David J. Abel , Beng Chin Ooi , Kian-Lee Tan , Robert Power , Jeffrey X. Yu, Spatial Join Strategies in Distributed Spatial DBMS, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.348-367, August 06-09, 1995
• 3: Ning An , Zhen-Yu Yang , Anand Sivasubramaniam, Selectivity Estimation for Spatial Joins, Proceedings of the 17th International Conference on Data Engineering, p.368-375, April 02-06, 2001
• 4: 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.
• 5: Walid G. Aref , Hanan Samet, Hashing by proximity to process duplicates in spatial databases, Proceedings of the third international conference on Information and knowledge management, p.347-354, November 29-December 02, 1994, Gaithersburg, Maryland, United States [doi>10.1145/191246.191307]
• 6: 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.
• 7: Walid G. Aref , Hanan Samet, Cascaded spatial join algorithms with spatially sorted output, Proceedings of the 4th ACM international workshop on Advances in geographic information systems, p.17-24, November 1996, Rockville, Maryland, United States [doi>10.1145/258319.258327]
• 8: Lars Arge , Klaus Hinrichs , Jan Vahrenhold , Jeffrey Scott Vitter, Efficient Bulk Operations on Dynamic R-trees, Selected papers from the International Workshop on Algorithm Engineering and Experimentation, p.328-348, January 15-16, 1999
• 9: Lars Arge , Octavian Procopiuc , Sridhar Ramaswamy , Torsten Suel , Jan Vahrenhold , Jeffrey Scott Vitter, A Unified Approach for Indexed and Non-Indexed Spatial Joins, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.413-429, March 27-31, 2000
• 10: Lars Arge , Octavian Procopiuc , Sridhar Ramaswamy , Torsten Suel , Jeffrey Scott Vitter, Scalable Sweeping-Based Spatial Join, Proceedings of the 24rd International Conference on Very Large Data Bases, p.570-581, August 24-27, 1998
• 11: Wael M. Badawy , Walid G. Aref, On local heuristics to speed up polygon-polygon intersection tests, Proceedings of the 7th ACM international symposium on Advances in geographic information systems, p.97-102, November 02-06, 1999, Kansas City, Missouri, United States [doi>10.1145/320134.320160]
• 12: Ivan J. Balaban, An optimal algorithm for finding segments intersections, Proceedings of the eleventh annual symposium on Computational geometry, p.211-219, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220302]
• 13: Ludger Becker , Klaus Hinrichs , Ulrich Finke, A New Algorithm for Computing Joins with Grid Files, Proceedings of the Ninth International Conference on Data Engineering, p.190-197, April 19-23, 1993
• 14: A. Belussi , E. Bertino , A. Nucita, Grid based methods for estimating spatial join selectivity, Proceedings of the 12th annual ACM international workshop on Geographic information systems, November 12-13, 2004, Washington DC, USA [doi>10.1145/1032222.1032238]
• 15: Alberto Belussi , Christos Faloutsos, Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension, Proceedings of the 21th International Conference on Very Large Data Bases, p.299-310, September 11-15, 1995
• 16: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 17: Thomas Brinkhoff , Hans-Peter Kriegel, Approximations for a Multi-Step Processing of Spatial Joins, Proceedings of the International Workshop on Advanced Information Systems: Geographic Information Systems, p.25-34, February 28-March 04, 1994
• 18: Thomas Brinkhoff , Hans-Peter Kriegel, The Impact of Global Clustering on Spatial Database Systems, Proceedings of the 20th International Conference on Very Large Data Bases, p.168-179, September 12-15, 1994
• 19: Thomas Brinkhoff , Hans-Peter Kriegel , Ralf Schneider, Comparison of Approximations of Complex Objects Used for Approximation-based Query Processing in Spatial Database Systems, Proceedings of the Ninth International Conference on Data Engineering, p.40-49, April 19-23, 1993
• 20: Thomas Brinkhoff , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, Multi-step processing of spatial joins, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.197-208, May 24-27, 1994, Minneapolis, Minnesota, United States
• 21: Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Efficient processing of spatial joins using R-trees, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.237-246, May 25-28, 1993, Washington, D.C., United States
• 22: Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Parallel Processing of Spatial Joins Using R-trees, Proceedings of the Twelfth International Conference on Data Engineering, p.258-265, February 26-March 01, 1996
• 23: 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.
• 24: Bernard Chazelle , Herbert Edelsbrunner, An optimal algorithm for intersecting line segments in the plane, Journal of the ACM (JACM), v.39 n.1, p.1-54, Jan. 1992 [doi>10.1145/147508.147511]
• 25: N. Chiba , T. Nishizeki, The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs, Journal of Algorithms, v.10 n.2, p.187-211, June 1989 [doi>10.1016/0196-6774(89)90012-6]
• 26: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 27: Antonio Corral , Michael Vassilakopoulos , Yannis Manolopoulos, Algorithms for Joining R-Trees and Linear Region Quadtrees, Proceedings of the 6th International Symposium on Advances in Spatial Databases, p.251-269, July 20-23, 1999
• 28: Abhinandan Das , Johannes Gehrke , Mirek Riedewald, Approximation techniques for spatial data, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007646]
• 29: 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.
• 30: Data Redundancy and Duplicate Detection in Spatial Join Processing, Proceedings of the 16th International Conference on Data Engineering, p.535, February 28-March 03, 2000
• 31: Edelsbrunner, H. 1983. A new approach to rectangle intersections: Part I. Int. J. Comput. Math. 13, 3--4, 209--219.
• 32: Ramez A. Elmasri , Shamkant B. Navathe, Fundamentals of Database Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 33: Jost Enderle , Matthias Hampel , Thomas Seidl, Joining interval data in relational databases, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007645]
• 34: Christos Faloutsos , Ibrahim Kamel, Beyond uniformity and independence: analysis of R-trees using the concept of fractal dimension, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.4-13, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182593]
• 35: Christos Faloutsos , Bernhard Seeger , Agma Traina , Caetano Traina, Jr., Spatial join selectivity using power laws, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.177-188, May 15-18, 2000, Dallas, Texas, United States
• 36: Finkel, R. A. and Bentley, J. L. 1974. Quad trees: A data structure for retrieval on composite keys. Acta Informatica 4, 1, 1--9.
• 37: F. Fotouhi , S. Pramanik, Optimal Secondary Storage Access Sequence for Performing Relational Join, IEEE Transactions on Knowledge and Data Engineering, v.1 n.3, p.318-328, September 1989 [doi>10.1109/69.87978]
• 38: Volker Gaede, Optimal Redundancy in Spatial Database Systems, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.96-116, August 06-09, 1995
• 39: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 40: Hector Garcia-Molina , Jennifer Widom , Jeffrey D. Ullman, Database System Implementation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 41: S. Gottschalk , M. C. Lin , D. Manocha, OBBTree: a hierarchical structure for rapid interference detection, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.171-180, August 1996 [doi>10.1145/237170.237244]
• 42: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 43: Oliver Günther, Efficient Computation of Spatial Joins, Proceedings of the Ninth International Conference on Data Engineering, p.50-59, April 19-23, 1993
• 44: Oliver Günther , Vincent Oria , Philippe Picouet , Jean-Marc Saglio , Michel Scholl, Benchmarking Spatial Joins À La Carte, Proceedings of the 10th International Conference on Scientific and Statistical Database Management, p.32-41, July 01-03, 1998 [doi>10.1109/SSDM.1998.688109]
• 45: Christophe Gurret , Philippe Rigaux, The Sort/Sweep Algorithm: A New Method for R-tree Based Spatial Joins, Proceedings of the 12th International Conference on Scientific and Statistical Database Management (SSDBM'00), p.153, July 26-28, 2000 [doi>10.1109/SSDM.2000.869785]
• 46: Ralf Harmut Güting , Werner Schilling, A practical divide-and-conquer algorithm for the rectangle intersection problem, Information Sciences: an International Journal, v.42 n.2, p.95-112, July 1987 [doi>10.1016/0020-0255(87)90018-1]
• 47: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 48: 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.
• 49: Lilian Harada , Miyuki Nakano , Masaru Kitsuregawa , Mikio Takagi, Query Processing for Multi-Attribute Clustered Records, Proceedings of the 16th International Conference on Very Large Data Bases, p.59-70, August 13-16, 1990
• 50: Joseph M. Hellerstein , Jeffrey F. Naughton , Avi Pfeffer, Generalized Search Trees for Database Systems, Proceedings of the 21th International Conference on Very Large Data Bases, p.562-573, September 11-15, 1995
• 51: Gísli R. Hjaltason , Hanan Samet, Improved bulk-loading algorithms for quadtrees, Proceedings of the 7th ACM international symposium on Advances in geographic information systems, p.110-115, November 02-06, 1999, Kansas City, Missouri, United States [doi>10.1145/320134.320162]
• 52: 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.
• 53: Erik G. Hoel , Hanan Samet, Benchmarking Spatial Join Operations with Spatial Output, Proceedings of the 21th International Conference on Very Large Data Bases, p.606-618, September 11-15, 1995
• 54: Yun-Wu Huang , Ning Jing , Elke A. Rundensteiner, A Cost Model for Estimating the Performance of Spatial Joins Using R-trees, Proceedings of the Ninth International Conference on Scientific and Statistical Database Management, p.30-38, August 11-13, 1997 [doi>10.1109/SSDM.1997.621148]
• 55: Yun-Wu Huang , Ning Jing , Elke A. Rundensteiner, Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations, Proceedings of the 23rd International Conference on Very Large Data Bases, p.396-405, August 25-29, 1997
• 56: Edwin H. Jacox , Hanan Samet, Iterative spatial join, ACM Transactions on Database Systems (TODS), v.28 n.3, p.230-256, September 2003 [doi>10.1145/937598.937600]
• 57: Sang-Wook Kim , Wan-Sup Cho , Min-Jae Lee , Kyu-Young Whang, A New Algorithm for Processing Joins Using the Multilevel Grid File, Proceedings of the 4th International Conference on Database Systems for Advanced Applications (DASFAA), p.115-123, April 11-13, 1995
• 58: Masaru Kitsuregawa , Lilian Harada , Mikio Takagi, Join Strategies on KB-Tree Indexed Relations, Proceedings of the Fifth International Conference on Data Engineering, p.85-93, February 06-10, 1989
• 59: Knuth, D. E. 1973. The Art of Computer Programming: Sorting and Searching, vol. 3. Addison-Wesley, Reading, MA.
• 60: Nick Koudas , Kenneth C. Sevcik, Size separation spatial join, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.324-335, May 11-15, 1997, Tucson, Arizona, United States
• 61: Nick Koudas , Kenneth C. Sevcik, High Dimensional Similarity Joins: Algorithms and Performance Evaluation, Proceedings of the Fourteenth International Conference on Data Engineering, p.466-475, February 23-27, 1998
• 62: Vipin Kumar, Algorithms for constraint-satisfaction problems: a survey, AI Magazine, v.13 n.1, p.32-44, Spring 1992
• 63: Ming-Ling Lo , Chinya V. Ravishankar, Spatial joins using seeded trees, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.209-220, May 24-27, 1994, Minneapolis, Minnesota, United States
• 64: Ming-Ling Lo , Chinya V. Ravishankar, Generating Seeded Trees from Data Sets, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.328-347, August 06-09, 1995
• 65: Ming-Ling Lo , Chinya V. Ravishankar, Spatial hash-joins, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.247-258, June 04-06, 1996, Montreal, Quebec, Canada
• 66: 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.
• 67: A Non-Blocking Parallel Spatial Join Algorithm, Proceedings of the 18th International Conference on Data Engineering, p.697, February 26-March 01, 2002
• 68: 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.
• 69: 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.
• 70: Nikos Mamoulis , Dimitris Papadias, Integration of spatial join algorithms for processing multiple inputs, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.1-12, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 71: Nikos Mamoulis , Dimitris Papadias, Multiway spatial joins, ACM Transactions on Database Systems (TODS), v.26 n.4, p.424-475, December 2001 [doi>10.1145/503099.503101]
• 72: Nikos Mamoulis , Dimitris Papadias, Selectivity Estimation of Complex Spatial Queries, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.155-174, July 12-15, 2001
• 73: Nikos Mamoulis , Dimitris Papadias, Slot Index Spatial Join, IEEE Transactions on Knowledge and Data Engineering, v.15 n.1, p.211-231, January 2003 [doi>10.1109/TKDE.2003.1161591]
• 74: Nikos Mamoulis , Dimitris Papadias, Constraint-based algorithms for computing clique intersection joins, Proceedings of the 6th ACM international symposium on Advances in geographic information systems, p.118-123, November 02-07, 1998, Washington, D.C., United States [doi>10.1145/288692.288714]
• 75: McCreight, E. M. 1985. Priority search trees. SIAM J. Comput. 14, 2 (May), 257--276.
• 76: 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.
• 77: Priti Mishra , Margaret H. Eich, Join processing in relational databases, ACM Computing Surveys (CSUR), v.24 n.1, p.63-113, March 1992 [doi>10.1145/128762.128764]
• 78: Randal C. Nelson , Hanan Samet, A population analysis for hierarchical data structures, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.270-277, May 27-29, 1987, San Francisco, California, United States
• 79: Gabriele Neyer , Peter Widmayer, Singularities Make Spatial Join Scheduling Hard, Proceedings of the 8th International Symposium on Algorithms and Computation, p.293-302, December 17-19, 1997
• 80: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• 81: Jack A. Orenstein, Spatial query processing in an object-oriented database system, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.326-336, May 28-30, 1986, Washington, D.C., United States
• 82: J. A. Orenstein, Redundancy in spatial databases, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.295-305, June 1989, Portland, Oregon, United States
• 83: J. A. Orenstein, Strategies for optimizing the use of redundancy in spatial databases, Proceedings of the first symposium on Design and implementation of large spatial databases, p.115-134, February 1990, Santa Barbara, California, United States
• 84: J. A. Orenstein , F. A. Manola, PROBE Spatial Data Modeling and Query Processing in an Image Database Application, IEEE Transactions on Software Engineering, v.14 n.5, p.611-629, May 1988 [doi>10.1109/32.6139]
• 85: Thomas Ottmann , Derick Wood, Space-economical plane-sweep algorithms, Computer Vision, Graphics, and Image Processing, v.34 n.1, p.35-51, April 1986 [doi>10.1016/0734-189X(86)90046-0]
• 86: M. Tamer Özsu , Patrick Valduriez, Principles of distributed database systems (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 87: Dimitris Papadias , Dinos Arkoumanis, Approximate Processing of Multiway Spatial Joins in Very Large Databases, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.179-196, March 25-27, 2002
• 88: Dimitris Papadias , Nikos Mamoulis , Vasilis Delis, Algorithms for Querying by Spatial Structure, Proceedings of the 24rd International Conference on Very Large Data Bases, p.546-557, August 24-27, 1998
• 89: Dimitris Papadias , Nikos Mamoulis , Yannis Theodoridis, Processing and optimization of multiway spatial joins using R-trees, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.44-55, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303981]
• 90: Apostolos Papadopoulos , Philippe Rigaux , Michel Scholl, A Performance Evaluation of Spatial Join Processing Strategies, Proceedings of the 6th International Symposium on Advances in Spatial Databases, p.286-307, July 20-23, 1999
• 91: Ho-Hyun Park , Guang-Ho Cha , Chin-Wan Chung, Multi-way Spatial Joins Using R-Trees: Methodology and Performance Evaluation, Proceedings of the 6th International Symposium on Advances in Spatial Databases, p.229-250, July 20-23, 1999
• 92: Ho-Hyun Park , Chan-Gun Lee , Yong-Ju Lee , Chin-Wan Chung, Early Separation of Filter and Refinement Steps in Spatial Query Optimization, Proceedings of the Sixth International Conference on Database Systems for Advanced Applications, p.161-168, April 19-21, 1999
• 93: Jignesh M. Patel , David J. DeWitt, Partition based spatial-merge join, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.259-270, June 04-06, 1996, Montreal, Quebec, Canada
• 94: Jignesh M. Patel , David J. DeWitt, Clone join and shadow join: two parallel spatial join algorithms, Proceedings of the 8th ACM international symposium on Advances in geographic information systems, p.54-61, November 06-11, 2000, Washington, D.C., United States [doi>10.1145/355274.355282]
• 95: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 96: William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]
• 97: 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.
• 98: Doron Rotem, Spatial Join Indices, Proceedings of the Seventh International Conference on Data Engineering, p.500-509, April 08-12, 1991
• 99: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 100: Hanan Samet, Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 101: Bernhard Seeger, Performance Comparison of Segment Access Methods Implemented on Top of the Buddy-Tree, Proceedings of the Second International Symposium on Advances in Spatial Databases, p.277-296, August 28-30, 1991
• 102: Ju-Won Song , Kyu-Young Whang , Young-Koo Lee , Min-Jae Lee , Sang-Wook Kim, Spatial Join Processing Using Corner Transformation, IEEE Transactions on Knowledge and Data Engineering, v.11 n.4, p.688-695, July 1999 [doi>10.1109/69.790844]
• 103: Chengyu Sun , Divyakant Agrawal , Amr El Abbadi, Hardware acceleration for spatial selections and joins, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872813]
• 104: Kian-Lee Tan , Beng Chin Ooi , David J. Abel, Exploiting Spatial Indexes for Semijoin-Based Join Processing in Distributed Spatial Databases, IEEE Transactions on Knowledge and Data Engineering, v.12 n.6, p.920-937, November 2000 [doi>10.1109/69.895802]
• 105: Yannis Theodoridis , Emmanuel Stefanakis , Timos K. Sellis, Cost Models for Join Queries in Spatial Databases, Proceedings of the Fourteenth International Conference on Data Engineering, p.476-483, February 23-27, 1998
• 106: Ulrich, T. 2000. Loose octrees. In Game Programming Gems, M. A. DeLoura, Ed. Charles River Media, Rockland, MA. 444--453.
• 107: Jochen Van den Bercken , Bernhard Seeger , Peter Widmayer, A Generic Approach to Bulk Loading Multidimensional Index Structures, Proceedings of the 23rd International Conference on Very Large Data Bases, p.406-415, August 25-29, 1997
• 108: The Bulk Index Join: A Generic Approach to Processing Non-Equijoins, Proceedings of the 15th International Conference on Data Engineering, p.257, March 23-26, 1999
• 109: van Oosterom, P. 1994. An R-tree based map-overlay algorithm. In EGIS/MARI: 5th European Conference on Geographical Information Systems (Paris). 318--327.
• 110: 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.
• 111: 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.
• 112: 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.
• 113: Hein M. Veenhof , Peter M. G. Apers , Maurice A. W. Houtsma, Optimisation of Spatial Joins Using Filters, Proceedings of the 13th British National Conference on Databases: Advances in Databases, p.136-154, July 12-14, 1995
• 114: Kyu-Young Whang , Ravi Krishnamurthy, The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure, Proceedings of the Second International Symposium on Database Systems for Advanced Applications, p.449-459, April 02-04, 1991
• 115: Xiaofang Zhou , David J. Abel , David Truffet, Data Partitioning for Parallel Spatial Join Processing, Proceedings of the 5th International Symposium on Advances in Spatial Databases, p.178-196, July 15-18, 1997
• 116: Hongjun Zhu , Jianwen Su , Oscar H. Ibarra, Extending Rectangle Join Algorithms for Rectilinear Polygons, Proceedings of the First International Conference on Web-Age Information Management, p.247-258, June 21-23, 2000
• 117: Hongjun Zhu , Jianwen Su , Oscar H. Ibarra, Toward Spatial Joins for Polygons, Proceedings of the 12th International Conference on Scientific and Statistical Database Management (SSDBM'00), p.231, July 26-28, 2000 [doi>10.1109/SSDM.2000.869791]
• 118: Hongjun Zhu , Jianwen Su , Oscar H. Ibarra, On Multi-way Spatial Joins with Direction Predicates, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.217-235, July 12-15, 2001
• 119: Manli Zhu , Dimitris Papadias , Jun Zhang , Dik Lun Lee, Top-k Spatial Joins, IEEE Transactions on Knowledge and Data Engineering, v.17 n.4, p.567-579, April 2005 [doi>10.1109/TKDE.2005.65]
• 120: Geraldo Zimbrao , Jano Moreira de Souza, A Raster Approximation For Processing of Spatial Joins, Proceedings of the 24rd International Conference on Very Large Data Bases, p.558-569, August 24-27, 1998

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Algorithms, Design

Keywords:
External memory algorithms, plane-sweep, spatial join