Advertisement

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)

Abstract

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.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  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