A spatial hash join algorithm suited for small buffer size

ABSTRACT

In this paper, a new algorithm for spatial join operations is introduced. The so-called NRQB (No Replication with Quadtrees and Buckets Spatial Merge Join) enhances the original PBSM by partitioning the space according to the spatial distribution of the objects. In addition, a hash file is created for each input data set and used to enhance both the storage of and the access to the minimum bounding rectangles (MBR) of the respective set elements. The paper also presents a performance evaluation of the proposed algorithm relying on the results obtained by the execution of a series of test cases concerning different spatial join scenarios. In each test case, the response time of NRQB is compared with that of some well-known algorithms. The test cases were conducted with both synthetic and real data sets. The results showed that the new algorithm is best suited for smaller buffer sizes, which are typical of mobile devices and database systems for desktop computers.

REFERENCES

• 1: 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
• 2: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 3: A. Belussi, E. Bertino, and A. Nucita. Grid based methods for spatial join stimation. In 11th Symposium of Advanced Databases Systems, pages 49--60, 2003.
• 4: Thomas Brinkhoff, A Robust and Self-tuning Page-Replacement Strategy for Spatial Database Systems, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.533-552, March 25-27, 2002
• 5: 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
• 6: 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
• 7: M. R. Fornari and C. Iochpe. A new algorithm for spatial join based on space subdivision. In 11th Symposium of Advanced Databases Systems, pages 69--81, 2003.
• 8: 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]
• 9: Henry F. Korth , Abraham Silberschatz, Database System Concepts, McGraw-Hill, Inc., New York, NY, 1990
• 10: 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
• 11: 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
• 12: S. D. G. G. C. MAGALHES. A comparison among different syncronized tree transversal algorithms for spatial joins. In GEOINFO 2000, 2000. Available at www.geoinfo.info.
• 13: 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
• 14: P. Rigaux, M. Scholl, and A. Voisard. Spatial Databases with Applications to GIS. Morgan Kaufmann Pub., San Franscisco:USA, 2000.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

General Terms:
Algorithms, Performance

Keywords:
GIS, geographic databases, hash, spatial join