Abstract
The contributions of the paper span theoretical and implementational results. First, we prove that Kd-trees can be extended to ℝ^d with the distance measured by an arbitrary Bregman divergence. Perhaps surprisingly, this shows that the triangle inequality is not necessary for correct pruning in Kd-trees. Second, we offer an efficient algorithm and C++ implementation for nearest neighbour search for decomposable Bregman divergences. The implementation supports the Kullback-Leibler divergence (relative entropy) which is a popular distance between probability vectors and is commonly used in statistics and machine learning. This is a step toward broadening the usage of computational geometry algorithms. Our benchmarks show that our implementation efficiently handles both exact and approximate nearest neighbour queries. Compared to a linear search, we achieve two orders of magnitude speedup for practical scenarios in dimension up to 100. Our solution is simpler and more efficient than competing methods.
Keywords
InferenceEstimatorUpper and lower boundsLatent variableDifferentiable functionBayes' theoremComputer sciencePosterior probabilityBayesian inferenceAlgorithmProbabilistic logicMathematicsApplied mathematicsArtificial intelligenceBayesian probabilityStatistics
Related Publications
Game theory, maximum entropy, minimum discrepancy and robust Bayesian decision theory
We describe and develop a close relationship between two problems that have customarily been regarded as distinct: that of maximizing entropy, and that of minimizing worst-case ...
Variational Inference: A Review for Statisticians
One of the core problems of modern statistics is to approximate difficult-to-compute probability densities. This problem is especially important in Bayesian statistics, which fr...
Inducing features of random fields
We present a technique for constructing random fields from a set of training samples. The learning paradigm builds increasingly complex fields by allowing potential functions, o...
Multi-way Clustering on Relation Graphs
A number of real-world domains such as social networks and e-commerce involve heterogeneous data that describes relations between multiple classes of entities.Understanding the ...
Mitochondrial DNA phylogeography of European hedgehogs
European hedgehog populations belonging to Erinaceus europaeus and E . concolor have been investigated by mitochondrial DNA analysis. A 383 bp fragment of the cytochrome b gene ...
Publication Info
- Year
- 2025
- Type
- preprint
- Citations
- 1878
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
1878
OpenAlex
Cite This
Diederik P. Kingma,
Max Welling
(2025).
Fast Kd-Trees for the Kullback-Leibler Divergence and Other Decomposable Bregman Divergences.
Wiardi Beckman Foundation (Wiardi Beckman Foundation)
.
https://doi.org/10.4230/lipics.wads.2025.45
Identifiers
- DOI
- 10.4230/lipics.wads.2025.45