Nearest neighbor search on total bregman balls tree

In high-dimensional spaces, a near neighbor search (NNS) has a high computational cost, which has motivated research toward the development of (NNS) methods based on data structures. These structures open the possibility that only one part of the data set needs to be examined, thus decreasing the computational cost. The NNS methods are in their greater part based on metric properties of the adopted similarity measure. However, there exist real applications that involve, for example, the comparison of probabilities, images, among others, and for which the adequate notion of similarity cannot be defined by a metric. In this study we present a new data structure and a new algorithm for NNS using Total Bregman Divergence (TBD). The TBD is invariant in relation to rotation of the coordinate axes and allows for the definition of centers, which are robust to noisy data. The structure and the proposed search method allow for the development of meta-algorithms, which are applicable to any TBD. The experiment presented herein shows the good performance of the new structure in the NNS methods.