Bregman vantage point trees for efficient nearest Neighbor Queries

Frank Nielsen, Paolo Piro, Michel Barlaud

Abstract

Nearest neighbor (NN) retrieval is a crucial tool of many computer vision tasks. Since the brute-force naive search is too time consuming for most applications, several tailored data structures have been proposed to improve the efficiency of NN search. Among these, vantage point tree (vp-tree) was introduced for information retrieval in metric spaces. Vptrees have recently shown very good performances for image patch retrieval with respect to the L <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> metric. In this paper we generalize the seminal vp-tree construction and search algorithms to the broader class of Bregman divergences. These distorsion measures are preferred in many cases, as they also handle entropic distances (e.g., Kullback-Leibler divergence) besides quadratic distances. We also extend vp-tree to deal with symmetrized Bregman divergences, which are commonplace in applications of content-based multimedia retrieval. We evaluated performances of our Bvp-tree for exact and approximate NN search on two image feature datasets. Our results show good performances of Bvp-tree, specially for symmetrized Bregman NN queries.
BibTeX
@inproceedings{nielsen2009bregman,
  author = {Frank Nielsen and Paolo Piro and Michel Barlaud},
  title = {{Bregman vantage point trees for efficient nearest Neighbor Queries}},
  booktitle = {ICME},
  year = {2009},
  doi = {10.1109/icme.2009.5202635},
}

Loading related content...

Figure