Bregman proximity queries

Problem: Given a query point, find the k nearest neighbors with respect to a Bregman divergence, or a symmetrized Bregman divergence (that is not of Bregman-type except for squared Mahalanobis distances). Bregman ball trees (BBTs) and Bregman Vantange Point treees (BVPTs) data structures have proved to be very effective for image retrieval applications.

C++ source codes

(developed by Paolo Piro)

Illustrations for the BVPTs

Bregman divergence One point/leaf Ten points/leaf
L22 (squared Euclidean)
eKL (extended Kullback-Leibler)
Download all figures:


Frank Nielsen, last updated July 2016.