dc.contributor |
Aluja Banet, Tomàs |
dc.contributor.author |
Si, Peng |
dc.date |
2011-09-05 |
dc.identifier.uri |
http://hdl.handle.net/2099.1/13110 |
dc.language.iso |
eng |
dc.publisher |
Universitat Politècnica de Catalunya |
dc.rights |
Attribution-NonCommercial-NoDerivs 3.0 Spain |
dc.rights |
info:eu-repo/semantics/openAccess |
dc.rights |
http://creativecommons.org/licenses/by-nc-nd/3.0/es/ |
dc.subject |
Àrees temàtiques de la UPC::Enginyeria de la telecomunicació::Processament del senyal::Reconeixement de formes |
dc.subject |
Pattern recognition systems |
dc.subject |
Reconeixement de formes (Informàtica) |
dc.title |
Approximate nearest neighbour search with the fukunaga & narendra algorithm |
dc.type |
info:eu-repo/semantics/masterThesis |
dc.description.abstract |
English: Nearest neighbour search is the one of the most simple and used technique in
Pattern Recognition due to its simplicity and its good behaviour..
Many fast NN search algorithm have been developed during last years. However,
in some classifacation tasks an exact NN search is too slow, and a way to quicken the
search is required. To face these tasks it is possible to use approximate NN search, which
usually increases error rates but highly reduces search time.
One of the most known faster nearest neighbour algorithms was proposed by
Fugunada and Naendra. There are two way to perfoem the algorithm: building a tree or
performing clustering(classic way) in process time that is traversed on search time using
some elimination rules to avoid its full exploration. This paper tests one type of the
improvement in a real data environment. A new priority list is invited in order to reduce
significant both: the number of distance computations and the search time expended to
find the nearest neighbour.
This work has been developed on the program R-project version 2.13.1. over a
computer with Windows Vista 32 bits, CPU: AMD Athlon X2 Dual-Duo CPU 2.00GHz
and RAM: 2038 MB. |