About
Contact
Help
Sending publications
How to publish
Advanced Search
View Item 
  •   Home
  • Facultad de Ciencias Físicas y Matemáticas
  • Artículos de revistas
  • View Item
  •   Home
  • Facultad de Ciencias Físicas y Matemáticas
  • Artículos de revistas
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse byCommunities and CollectionsDateAuthorsTitlesSubjectsThis CollectionDateAuthorsTitlesSubjects

My Account

Login to my accountRegister
Biblioteca Digital - Universidad de Chile
Revistas Chilenas
Repositorios Latinoamericanos
Tesis LatinoAmericanas
Tesis chilenas
Related linksRegistry of Open Access RepositoriesOpenDOARGoogle scholarCOREBASE
My Account
Login to my accountRegister

Practical construction of k-nearest neighbor graphs in metric spaces

Artículo
Thumbnail
Open/Download
IconParedes_Rodrigo.pdf (191.6Kb)
Publication date
2006
Metadata
Show full item record
Cómo citar
Paredes, Rodrigo
Cómo citar
Practical construction of k-nearest neighbor graphs in metric spaces
.
Copiar
Cerrar

Author
  • Paredes, Rodrigo;
  • Chávez, Edgar;
  • Figueroa, Karina;
  • Navarro, Gonzalo;
Abstract
Let U be a set of elements and d a distance function defined among them. Let NNk (u) be the k elements in U - {u} having the smallest distance to u. The k-nearest neighbor graph (kNNG) is a weighted directed graph G(U,E) such that E = {(u,v), v is an element of NNk(u)}. Several kNNG construction algorithms are known, but they are not suitable to general metric spaces. We present a general methodology to construct kNNGS 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.
Identifier
URI: https://repositorio.uchile.cl/handle/2250/124959
ISSN: 0302-9743
Quote Item
EXPERIMENTAL ALGORITHMS, PROCEEDINGS Book Series: LECTURE NOTES IN COMPUTER SCIENCE Volume: 4007 Pages: 85-97 Published: 2006
Collections
  • Artículos de revistas
xmlui.footer.title
31 participating institutions
More than 73,000 publications
More than 110,000 topics
More than 75,000 authors
Published in the repository
  • How to publish
  • Definitions
  • Copyright
  • Frequent questions
Documents
  • Dating Guide
  • Thesis authorization
  • Document authorization
  • How to prepare a thesis (PDF)
Services
  • Digital library
  • Chilean academic journals portal
  • Latin American Repository Network
  • Latin American theses
  • Chilean theses
Dirección de Servicios de Información y Bibliotecas (SISIB)
Universidad de Chile

© 2020 DSpace
  • Access my account