A Robust Method for Finding Nearest-Neighbor using Hexagon Cells

Authors: Ahmad Attiq Al-Ogaibi, Ahmad Sharieh, Moh’d Belal Al-Zoubi, R. Bremananth

Abstract:

In pattern clustering, nearest neighborhood point computation is a challenging issue for many applications in the area of research such as Remote Sensing, Computer Vision, Pattern Recognition and Statistical Imaging. Nearest neighborhood computation is an essential computation for providing sufficient classification among the volume of pixels (voxels) in order to localize the active-region-of-interests (AROI). Furthermore, it is needed to compute spatial metric relationships of diverse area of imaging based on the applications of pattern recognition. In this paper, we propose a new methodology for finding the nearest neighbor point, depending on making a virtually grid of a hexagon cells, then locate every point beneath them. An algorithm is suggested for minimizing the computation and increasing the turnaround time of the process. The nearest neighbor query points Φ are fetched by seeking fashion of hexagon holistic. Seeking will be repeated until an AROI Φ is to be expected. If any point Υ is located then searching starts in the nearest hexagons in a circular way. The First hexagon is considered be level 0 (L0) and the surrounded hexagons is level 1 (L1). If Υ is located in L1, then search starts in the next level (L2) to ensure that Υ is the nearest neighbor for Φ. Based on the result and experimental results, we found that the proposed method has an advantage over the traditional methods in terms of minimizing the time complexity required for searching the neighbors, in turn, efficiency of classification will be improved sufficiently.

Keywords: Hexagon cells, k-nearest neighbors, Nearest Neighbor, Pattern recognition, Query pattern, Virtually grid

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1336550

References:

[1] Ahmad Al-Ogaili, "Nearest Neighbor Searching using Hexagonal Cell”, M.Sc. Thesis, The University of Jordan, 2010.
[2] Sunil Arya, David M. Mount, Nathan S. Netanyahu,Ruth Silverman,Angela Y. Wu,"An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions,” Journal of the ACM (JACM) JACM, Vol. 45 Issue 6, pp. 891-923, Nov. 1998.
[3] J. L. Bentley, "Multidimensional binary search trees used for associative searching,” Communications of the ACM, 18(9), pp. 509-517, 1975.
[4] Lawrence Cayton, Sanjoy Dasgupta,"A Learning Framework for Nearest Neighbor Search,” Proceedings of the Twenty-First Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 3-6, 2007.
[5] Kenneth L. Clarkson, "Nearest-Neighbor Searching and Metric Space Dimensions,” Tech. Report of Bell Labs, NJ, pp. 1-45, Oct. 2005.
[6] Andrew T. Hudak, Nicholas L. Crookston, Jeffrey S. Evans, David E. Hall, Michael J. Falkowski,"Nearest neighbor imputation of species-level, plot-scale forest structure attributes from LiDAR data,” Remote Sensing of Environment, No. 112, pp.2232-2245, 2008.
[7] David Marshall, "Nearest Neighbour Searching in High Dimensional Metric Space,” Master Thesis, Australian National University, 2006.
[8] Roberto Paredes and Enrique Vidal, "Learning Weighted Metrics to Minimize Nearest-Neighbor Classification Error,” IEEE Trans. on Patt. Anal. Mach. Int., vol. 28, No. 7, pp.1100-1110, JULY 2006.
[9] Sun, J., Tao, Y., Papadias, D., and Kollios,G., "Spatio-temporal join selectivity,” Information Systems Journal Elsevier. vol.31, no. 8 , pp. 793-813, 2006.
[10] P. Viswanath, K. Rajesh, C. Lavanya, Y.C.A. Padmanabha Reddy,"A Selective Incremental Approach for Transductive Nearest Neighbor Classification,” Proc. IEEE, 978-1-4244-9477-4/11, pp. 221-226, 2011.
[11] Hui W., "Nearest Neighbors by Neighborhood Counting,” IEEE TPAMI, vol. 28, no.6, pp. 942-953, June 2006.
[12] Xianfei Zhang, Bicheng Li, Xianzhu Sun, "A k-Nearest Neighbor Text Classification algorithm Based on Fuzzy Integral,” Proc. of IEEE, Sixth International Conference on Natural Computation (ICNC 2010), 978-1-4244-5961-2/10, pp. 2228-2231, 2010.