Bregman vantage point trees: VP-trees using Bregman balls for fast nearest-neighbor queries
FrnkNlsn · x · 2026-11-05
A share of Bregman vantage point trees, a generalization of VP-trees that partitions space using Bregman balls instead of Euclidean balls, enabling efficient nearest-neighbor queries under arbitrary Bregman divergences.
The accompanying figure visualizes the induced partitions under different divergences:
- (squared) Euclidean distance: classic circular regions
- extended Kullback-Leibler divergence
- Itakura-Saito divergence
Based on the ICME 2009 paper "Bregman vantage point trees for efficient nearest Neighbor Queries", with the radical axis of Bregman spheres as the key geometric tool. Useful for vector search under non-Euclidean metrics such as KL divergence.
More from Research
- Stanford benchmark: frontier models reach best team deal in only 14% of conflicts — rohanpaul_ai · 2026-11-05
- RL theory monograph by Chen, Chi, Fan et al: Statistical Foundations of RL, a non-asymptotic view — burny_tech · 2026-11-05
- Weight-space programming reproduced: GPT-6.1 beats PPO baseline 21x, no open-weight model passes it — burny_tech · 2026-11-05
- Chinese AI Scientist completes 11,382-step experiment in 203 hours autonomously — yogthos · 2026-11-05
- 8% of Nature peer reviews since June 2025 are fully AI-generated, analysis finds — TuhinChakr · 2026-11-05
- HandsOn benchmark: best dexterous manipulation policy manages only 29.1% success on Core-50 — jiqizhixin · 2026-11-05