Olá, pessoal.
Seguem alguns links que podem ser de interesse a respeito do método usado no artigo do SIFT para determinar aproximadamente os vizinhos mais próximos de um dado keypoint.
A primeira referência descreve o método adotado no artigo: Best bin first. Foi desenvolvido pelo próprio Lowe e Jeffrey Beis, e é descrito no seguinte artigo do CVPR97 ("Shape indexing using approximate nearest-neighbour search in high-dimensional spaces" ):
http://www.cs.ubc.ca/~lowe/papers/cvpr97.pdf
Como esse artigo traz uma variação de k-d-trees (k-dimensional trees), referências sobre k-d-trees também são interessantes:
http://en.wikipedia.org/wiki/Kd-tree
http://www.cs.cmu.edu/~awm/animations/kdtree/
Espero que sejam úteis.
Até mais,
Ana
ps: o livro do Duda & Hart traz uma discussão sobre árvores de decisão no capítulo 8. Porém, talvez haja algum material mais completo sobre isso...quem souber ou tiver sugestões, por favor, avise-nos.