Copyright and Licensing
Articles accepted for publication will be licensed under the Creative Commons BY-NC-SA. Authors must sign a non-exclusive distribution agreement after article acceptance.
All Near Neighbor GraphWithout Searching
DOI:
https://doi.org/10.24215/16666038.18.e07Keywords:
Near Neighbor Graph, Proximity Search, Clustering, Metric IndexingAbstract
Given a collection of n objects equipped with a distance function d(·, ·), the Nearest Neighbor Graph (NNG) consists in finding the nearest neighbor of each object in the collection. Without an index the total cost of NNG is quadratic. Using an index the cost would be sub-quadratic if the search for individual items is sublinear. Unfortunately, due to the so called curse of dimensionality the indexed and the brute force methods are almost equally inefficient. In this paper we present an efficient algorithm to build the Near Neighbor Graph (nNG), that is an approximation of NNG, using only the index construction, without actually searching for objects.
Downloads
Download data is not yet available.
References
[1] C.-H. Liu, E. Papadopoulou, and D.-T. Lee, “The k-nearest-neighbor voronoi diagram revisited,” Algorithmica, vol. 71, pp. 429–449, Feb. 2015.
[2] E. Ch´avez, G. Navarro, R. Baeza-Yates, and J. Marroquín, “Searching in metric spaces,” ACM Computing Surveys, vol. 33, pp. 273–321, Sept. 2001.
[3] R. Duda and P. Hart, “Pattern classification and scene analysis,” John Wiley & Sons, 1973.
[4] E. Chávez, V. Ludueña, N. Reyes, and P. Roggero, “Faster proximity searching with the distal sat,” Information Systems, vol. 59, pp. 15–47, 2016.
[5] E. Chávez, V. Ludueña, N. Reyes, and F. Kasián, “Approximate nearest neighbor graph via index construction,” pp. 824–833, 2016.
[6] G. Navarro, R. Paredes, N. Reyes, and C. Bustos, “An empirical evaluation of intrinsic dimension estimators,” Inf. Syst., vol. 64, pp. 206–218,Mar. 2017.
[7] M. Brito, E. Chávez, A. Quiroz, and J. Yukich, “Connectivity of the mutual k-nearest neighbor graph in clustering and outlier detection,” Statistics & Probability Letters, vol. 35, no. 4, pp. 33–42, 1996.
[8] D. Eppstein and J. Erickson, “Iterated nearest neighbors and finding minimal poly-topes,” vol. 11, pp. 321–350, 1994.
[9] N. Archip, R. Rohling, P. Cooperberg, H. Tahmasebpour, and S. K. Warfield, “Spectral clustering algorithms for ultrasound image segmentation,” vol. 3750, pp. 862–869, 2005.
[10] R. Baeza-Yates, C. Hurtado, and M. Mendoza, “Query clustering for boosting web page ranking,” pp. 164–175, 2004.
[11] P. Callahan and R. Kosaraju, “A decomposition of multidimensional point sets with applications to k nearest neighbors and n body potential fields,” JACM, vol. 42(1), pp. 67–90, 1995.
[12] R. Paredes, Graphs for Metric Space Searching. PhD thesis, University of Chile, Chile, July 2008.
[13] R. Paredes, E. Chávez, K. Figueroa, and G. Navarro, “Practical construction of k-nearest neighbor graphs in metric spaces,” in Proc. 5th Workshop on Efficient and Experimental Algorithms (WEA), LNCS 4007, pp. 85–97, 2006.
[14] P. Ciaccia and M. Patella, “Approximate and probabilistic methods,” SIGSPATIAL Special, vol. 2, no. 2, pp. 16–19, 2010.
[15] M. Patella and P. Ciaccia, “Approximate similarity search: A multifaceted problem,” J. Discrete Algorithms, vol. 7, no. 1, pp. 36–48, 2009.
[16] S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu, “An optimal algorithm for approximate nearest neighbor searching fixed dimensions,” J. ACM, vol. 45, pp. 891–923, Nov. 1998.
[17] G. Navarro, “Searching in metric spaces by spatial approximation,” The Very Large Databases Journal (VLDBJ), vol. 11, no. 1, pp. 28–46, 2002.
[18] G. Navarro and N. Reyes, “Dynamic spatial approximation trees,” Journal of Experimental Algorithmics, vol. 12, pp. 1–68, 2008.
[19] K. Figueroa, G. Navarro, and E. Chávez, “Metric spaces library,” 2007. Available at http://www.sisap.org/MetricSpaceLibrary.html.
[2] E. Ch´avez, G. Navarro, R. Baeza-Yates, and J. Marroquín, “Searching in metric spaces,” ACM Computing Surveys, vol. 33, pp. 273–321, Sept. 2001.
[3] R. Duda and P. Hart, “Pattern classification and scene analysis,” John Wiley & Sons, 1973.
[4] E. Chávez, V. Ludueña, N. Reyes, and P. Roggero, “Faster proximity searching with the distal sat,” Information Systems, vol. 59, pp. 15–47, 2016.
[5] E. Chávez, V. Ludueña, N. Reyes, and F. Kasián, “Approximate nearest neighbor graph via index construction,” pp. 824–833, 2016.
[6] G. Navarro, R. Paredes, N. Reyes, and C. Bustos, “An empirical evaluation of intrinsic dimension estimators,” Inf. Syst., vol. 64, pp. 206–218,Mar. 2017.
[7] M. Brito, E. Chávez, A. Quiroz, and J. Yukich, “Connectivity of the mutual k-nearest neighbor graph in clustering and outlier detection,” Statistics & Probability Letters, vol. 35, no. 4, pp. 33–42, 1996.
[8] D. Eppstein and J. Erickson, “Iterated nearest neighbors and finding minimal poly-topes,” vol. 11, pp. 321–350, 1994.
[9] N. Archip, R. Rohling, P. Cooperberg, H. Tahmasebpour, and S. K. Warfield, “Spectral clustering algorithms for ultrasound image segmentation,” vol. 3750, pp. 862–869, 2005.
[10] R. Baeza-Yates, C. Hurtado, and M. Mendoza, “Query clustering for boosting web page ranking,” pp. 164–175, 2004.
[11] P. Callahan and R. Kosaraju, “A decomposition of multidimensional point sets with applications to k nearest neighbors and n body potential fields,” JACM, vol. 42(1), pp. 67–90, 1995.
[12] R. Paredes, Graphs for Metric Space Searching. PhD thesis, University of Chile, Chile, July 2008.
[13] R. Paredes, E. Chávez, K. Figueroa, and G. Navarro, “Practical construction of k-nearest neighbor graphs in metric spaces,” in Proc. 5th Workshop on Efficient and Experimental Algorithms (WEA), LNCS 4007, pp. 85–97, 2006.
[14] P. Ciaccia and M. Patella, “Approximate and probabilistic methods,” SIGSPATIAL Special, vol. 2, no. 2, pp. 16–19, 2010.
[15] M. Patella and P. Ciaccia, “Approximate similarity search: A multifaceted problem,” J. Discrete Algorithms, vol. 7, no. 1, pp. 36–48, 2009.
[16] S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu, “An optimal algorithm for approximate nearest neighbor searching fixed dimensions,” J. ACM, vol. 45, pp. 891–923, Nov. 1998.
[17] G. Navarro, “Searching in metric spaces by spatial approximation,” The Very Large Databases Journal (VLDBJ), vol. 11, no. 1, pp. 28–46, 2002.
[18] G. Navarro and N. Reyes, “Dynamic spatial approximation trees,” Journal of Experimental Algorithmics, vol. 12, pp. 1–68, 2008.
[19] K. Figueroa, G. Navarro, and E. Chávez, “Metric spaces library,” 2007. Available at http://www.sisap.org/MetricSpaceLibrary.html.
Downloads
Published
2018-04-25
Issue
Section
Original Articles
License
How to Cite
[1]
“All Near Neighbor GraphWithout Searching”, JCS&T, vol. 18, no. 01, p. e07, Apr. 2018, doi: 10.24215/16666038.18.e07.
