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

bvp-tree_1.1.zip: Bregman Vantage Point Tree (BVPT)
bbtreepp.zip: Bregman ball tree++

(developed by Paolo Piro)

Illustrations for the BVPTs

Bregman divergence	One point/leaf	Ten points/leaf
L22 (squared Euclidean)
eKL (extended Kullback-Leibler)
Itakura-Saito

Download all figures: BVPfigs.zip.

References

Frank Nielsen, Paolo Piro, Michel Barlaud: Bregman vantage point trees for efficient nearest Neighbor Queries, ICME 2009: 878-881
Nielsen, Frank, Paolo Piro, and Michel Barlaud. Tailored Bregman ball trees for effective nearest neighbors , In Proceedings of the 25th European Workshop on Computational Geometry (EuroCG), pp. 29-32. 2009. eurocg09_presentation.pdf

Frank Nielsen, last updated July 2016.