Practical Construction of k-Nearest Neighbor Graphs in Metric Spaces

  • Rodrigo Paredes
  • Edgar Chávez
  • Karina Figueroa
  • Gonzalo Navarro
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4007)


Let \(\mathbb{U}\) be a set of elements and d a distance function defined among them. Let NN k (u) be the k elements in \(\mathbb{U}-\{u\}\) having the smallest distance to u. The k-nearest neighbor graph (k nng) is a weighted directed graph \(G(\mathbb{U},E)\) such that E = {(u,v), v ∈ NN k (u)}. Several k nng construction algorithms are known, but they are not suitable to general metric spaces. We present a general methodology to construct k nngs that exploits several features of metric spaces. Experiments suggest that it yields costs of the form c 1 n 1.27 distance computations for low and medium dimensional spaces, and c 2 n 1.90 for high dimensional ones.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Arya, S., Mount, D., Netanyahu, N., Silverman, R., Wu, A.: An optimal algorithm for approximate nearest neighbor searching in fixed dimension. In: Proc. SODA 1994, pp. 573–583 (1994)Google Scholar
  2. 2.
    Aurenhammer, F.: Voronoi diagrams – a survey of a fundamental geometric data structure. ACM Computing Surveys 23(3) (1991)Google Scholar
  3. 3.
    Baeza-Yates, R., Hurtado, C., Mendoza, M.: Query clustering for boosting web page ranking. In: Favela, J., Menasalvas, E., Chávez, E. (eds.) AWIC 2004. LNCS (LNAI), vol. 3034, pp. 164–175. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  4. 4.
    Brito, M., Chávez, E., Quiroz, A., Yukich, J.: Connectivity of the mutual k-nearest neighbor graph in clustering and outlier detection. Statistics & Probability Letters 35, 33–42 (1996)CrossRefGoogle Scholar
  5. 5.
    Callahan, P.: Optimal parallel all-nearest-neighbors using the well-separated pair decomposition. In: Proc. FOCS 1993, pp. 332–340 (1993)Google Scholar
  6. 6.
    Callahan, P., Kosaraju, R.: A decomposition of multidimensional point sets with applications to k nearest neighbors and n body potential fields. JACM 42(1), 67–90 (1995)CrossRefMathSciNetzbMATHGoogle Scholar
  7. 7.
    Chávez, E., Navarro, G.: A compact space decomposition for effective metric indexing. Pattern Recognition Letters 26(9), 1363–1376 (2005)CrossRefGoogle Scholar
  8. 8.
    Chávez, E., Navarro, G., Baeza-Yates, R., Marroquin, J.L.: Searching in metric spaces. ACM Computing Surveys 33(3), 273–321 (2001)CrossRefGoogle Scholar
  9. 9.
    Clarkson, K.: Fast algorithms for the all-nearest-neighbors problem. In: Proc. FOCS 1983, pp. 226–232 (1983)Google Scholar
  10. 10.
    Clarkson, K.: Nearest neighbor queries in metric spaces. Discrete Computational Geometry 22(1), 63–93 (1999)CrossRefMathSciNetzbMATHGoogle Scholar
  11. 11.
    Dickerson, M., Eppstein, D.: Algorithms for proximity problems in higher dimensions. Computational Geometry Theory and Applications 5, 277–291 (1996)MathSciNetzbMATHGoogle Scholar
  12. 12.
    Duda, R., Hart, P.: Pattern Classification and Scene Analysis. Wiley, Chichester (1973)zbMATHGoogle Scholar
  13. 13.
    Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Springer, Heidelberg (1987)zbMATHGoogle Scholar
  14. 14.
    Eppstein, D., Erickson, J.: Iterated nearest neighbors and finding minimal polytopes. Discrete & Computational Geometry 11, 321–350 (1994)CrossRefMathSciNetzbMATHGoogle Scholar
  15. 15.
    Figueroa, K.: An efficient algorithm to all k nearest neighbor problem in metric spaces. Master’s thesis, Universidad Michoacana, Mexico (in Spanish, 2000)Google Scholar
  16. 16.
    Hjaltason, G., Samet, H.: Incremental similarity search in multimedia databases. Technical Report TR 4199, Dept. of Comp. Sci. Univ. of Maryland (November 2000)Google Scholar
  17. 17.
    Kalantari, I., McDonald, G.: A data structure and an algorithm for the nearest point problem. IEEE Trans. Software Eng. 9(5), 631–634 (1983)CrossRefGoogle Scholar
  18. 18.
    Karger, D.R., Ruhl, M.: Finding nearest neighbors in growth-restricted metrics. In: Proc. STOC 2002, pp. 741–750 (2002)Google Scholar
  19. 19.
    Krauthgamer, R., Lee, J.: Navigating nets: simple algorithms for proximity search. In: Proc. SODA 2004, pp. 798–807 (2004)Google Scholar
  20. 20.
    Paredes, R., Chávez, E.: Using the k-nearest neighbor graph for proximity searching in metric spaces. In: Consens, M.P., Navarro, G. (eds.) SPIRE 2005. LNCS, vol. 3772, pp. 127–138. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  21. 21.
    R Development Core Team. R: A language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, Austria (2004)Google Scholar
  22. 22.
    Vaidya, P.: An O(nlogn) algorithm for the all-nearest-neighbor problem. Discrete & Computational Geometry 4, 101–115 (1989)CrossRefMathSciNetzbMATHGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Rodrigo Paredes
    • 1
  • Edgar Chávez
    • 2
  • Karina Figueroa
    • 1
    • 2
  • Gonzalo Navarro
    • 1
  1. 1.Center for Web Research, Dept. of Computer ScienceUniversity of Chile 
  2. 2.Escuela de Ciencias Físico-MatemáticasUniv. MichoacanaMexico

Personalised recommendations