Abstract

This paper identifies the scope for improvement in the execution of baseline kNN join algorithms in a distributed environment. Improvements are suggested and the improved methods are applied in performing kNN joins on R*-Trees. The effectiveness of the proposed improvements have been experimentally verified and presented.

References

• Jeffrey Dean and Sanjay Ghemawat, 2004, "Mapreduce: simplified data processing on large clusters", Proceedings of the 6th Conference on Symposium on Operating Systems Design & Implementation, vol. 6.
• Guttman, 1984, "R-trees: A dynamic index structure for spatial searching," Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 47-57.
• N. Beckmann, H. -P. Krieger, R. Schneider and B. Seeger, 1990, "The R*-tree: an efficient and robust access method for points and rectangles," Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 322-331.
• V. Gaede and 0. Guenther, 1998, "Multidimensional access methods," ACM Computing Surveys, vol. 30, no. 2, pp. 170-231.
• Y. Manolopoulos, A. Nanopoulos, A. N. Papadopoulos and Y. Theodoridis, 2003, "R-trees have grown everywhere," Technical Report, Available at http://citeseer. ist. psu. edu/706599. html.
• S. Brakatsoulas, D. Pfoser and Y. Theodoridis, 2002, "Revisiting R-tree construction principles," Proceedings of the 6th ADBIS Conference, pp. 149-162.
• L. Chen, R. Choubey and E. A. Rundensteiner, 1998, "Bulk-insertions into R-trees using the small-tree-large-tree approach," Proceedings of the 6th ACM GIS Conference, pp. 161-162.
• Daniar Achakeev, Marc Seidemann, Markus Schmidt and Bernhard Seeger, 2012, "Sort-based parallel loading of R-trees," Proceedings of the 1st ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, pp. 62-70.
• Faloutsos and I. Kamel, 1994, "Beyond uniformity and independence: Analysis of R-trees using the concept of fractal dimension," Proceedings of the 13th ACMPODS Conference, pp. 4-13.
• I. Kamel and C. Faloutsos, 1994, "Hilbert R-tree: An improved R-tree using fractals," Proceedings of the 20th International Conference on Very Large Databases, pp. 500-509.
• F. Sagayaraj Francis and P. Xavier, 2014, "Amendments to the R*-Tree Construction Principles in Distributed Environment", International Journal of Engineering Research & Technology, vol. 3, Issue 5.
• Christos Doulkeridis and Kjetil Norvag, 2013, "A Survey of Large-Scale Analytical Query Processing in Mapreduce," The VLDB Journal, DOI: 10. 1007/s00778-013-0319-9.
• Himanshu Gupta, Bhupesh Chawda, Sumit Negi, Tanveer A. Faruquie, L. V. Subramaniam and Mukesh Mohania, 2013, "Processing multi-way spatial joins on map-reduce," Proceedings of the 16th International Conference on Extending Database Technology, pp. 113-124.
• Afrati, F. N. and Ullman, J. D. , 2010, "Optimizing Joins in a Map-Reduce Environment", Proceedings of the 13th International Conference on Extending Database Technology, pp. 99–110.
• Nodarakis, N. ; Pitoura, E. ; Sioutas, S. ; Tsakalidis, A. ; Tsoumakos, D. ; and Tzimas, G. , 2014, "Efficient Multidimensional AkNN Query Processing in the Cloud", Proceeding of the 25th International Conference on Database and Expert Systems Applications, pp. 1016-1027.
• Lu, W. , Shen, Y. , Chen, S. and Ooi, B. C. , 2012, "Efficient Processing of k Nearest Neighbor Joins using Mapreduce", Proceedings of the VLDB Endowment, vol. 5, Issue 10.
• Chi Zhang, Feifei Li and Jeffrey Jestes, 2012, "Efficient parallel kNN joins for large data in Mapreduce," Proceedings of the 15th International Conference on Extending Database Technology, pp. 38-49.