Open Access Open Access  Restricted Access Subscription or Fee Access

A Study on Join Processing Techniques in Spatial Databases

Dr.E. Chandra, V.P. Anuradha


Query processing is an essential task to obtain meaningful information in a data mining application. It needs to be optimized for its effective implementation in any application. A join operation of relational data base management system is one such technique that can optimize the query process efficiently. In a similar manner the join operation in a spatial data base management system can be utilized to optimize the query process. Join operation itself is accelerated by the implementation of join indexes further optimizing the query process. Efficient implementation of join indices is possible with such multidimensional indexing structures as R-trees, Grid files, Bi-partite graphs, Neighbourhood graphs, etc. An effective join processing algorithm in collusion with the join index enhances the query process further. A cost model with CPU cost, I/O cost, number of page and node accesses with a constraint of fixed buffer size has to be evaluated to check the feasibility of the join operation.


Spatial Databases, Join Indices, Join Operation, Multidimensional Indexing Structures

Full Text:



L. Becker, K. Hinrichs, U. Finke, “A New Algorithm for Computing Joins with Grid Files”, IEEE, pp.190-197, 1993.

N. Beckmann, H. P. Kriegel, R. Schneider and B. Seeger, “The R*-tree: An Efficient and Robust Access Method for Points and Rectangles”, ACM, pp.322-331, 1990.

E.Chandra and V.P.Anuradha, “Heuristics for Optimal Page Access With Spatial Join Processing – An Analysis”, IEEE International Advance Computing Conference., pp. 2796-2800, Patiala, India, March, 2009.

E.Chandra and V.P.Anuradha, “Join Processing In Spatial Databases”,Second National Conference on Advanced Computing, pp. 233-237, September, 2010.

T. Cormen, C. Leiserson, and R. Rivest,”Introduction to Algorithms”, The MIT Press, 1991.

P. Goyal, H. F. Li, E. Regener, and F. Sadri, “Scheduling of Page Fetches in Join Operations Using Bc-Trees”, IEEE, pp.304-310, 1988.

O. Gunther, “Efficient Computation of Spatial Joins,” Proc. Int’l Conf. Data Eng., 1993.

A Guttman, “ R Trees: a Dynamic Index Structure for Spatial Searching”. In SIGMOD’84:Proceedings of the 1984 ACM SIGMOD international conference on Management of data, pp. 47-57, New York, NY, USA. 1984.

N.Mamoulis, D.Papadias and D.Arkoumanis. “Complex Spatial Query Processing”. GeoInformatica, Kluwer Academic Publishers, vol. 8, no. 4, 2004.

N. Mamoulis and D. Papadias, “Multiway Spatial Joins”, ACM Transactions on Database Systems, vol.26, no.4, pp. 424-475, December 2001

P. Mishra and Margaret H. Eich, “Join Processing In Relational Databases”, ACM Computing Surveys, vol. 24, no. 1,March 1992.

Mohan.P,Shekhar.S,Levine.N,Wilson.R.E,George.B and Celik.M, “Should SDBMS Support a Join Index?:A case Study from Crimestat”, ACM SIGSPATIAL, California, USA, 2008.

S. Shekhar, S. Chawla, “Spatial Databases-A Tour”, Pearson Education, 2009.

D. Rotem, “Spatial Join Indices”. In Proceedings of the Seventh International Conference on Data Engineering, April 8-12, 1991, Kobe Japan, pages 500-509. IEEE Computer Society, 1991.

P. Valduriez, “Join Indices”, ACM Transactions on Database Systems, vol.12, no.2, pp. 218-246, June 1987.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.