We consider the computational problem of finding nearest neighbors in metric and nonmetric spaces. Nonmetric spaces are the generalization of the general metric spaces but without requiring the triangular inequality assumption. Non-metric spaces are often encountered. Many of the similarity measures (between images, proteins, etc) do not verify the triangular inequality. The nonmetric case lead us to introduce a novel approach, to our knowledge, to the near neighbor search problem by introducing the notions of exploration and exploration accuracy profile. Those notions lead us to introduce a new search structure, called \emph{densitree} (contraction of ``density tree''),based on classifiers to estimate point densities in nonmetric spaces. Against well established datasets, our preliminary empirical results indicates that contrary to a common belief the triangular inequality (or an equivalent pruning criterion) is not required to perform efficient near-neighbor search. Additionally, the densitrees, although very naively implemented, seems to outperform existing methods both in metric and non-metric situation.