Abstract
In this paper we present the first provable approximate nearest-neighbor (ANN) algorithms for Bregman divergences. Our first algorithm processes queries in $O(\log^d n)$ time using $O(n \log^d n)$ space and only uses general properties of the underlying distance function (which includes Bregman divergences as a special case). The second algorithm processes queries in $O(\log n)$ time using $O(n)$ space and exploits structural constants associated specifically with Bregman divergences. An interesting feature of our algorithms is that they extend the ring-tree + quad-tree paradigm for ANN searching beyond Euclidean distances and metrics of bounded doubling dimension to distances that might not even be symmetric or satisfy a triangle inequality.
Introduction: Breaking the Metric Barrier
In machine learning and data science, the "nearest neighbor" search is a fundamental operation. For standard Euclidean distances, efficient tools like k-d trees or quad-trees allow searching millions of points in logarithmic time. These tools rely heavily on the triangle inequality: the geometric guarantee that the direct path between two points is always the shortest.
However, many critical real-world measures—such as the Kullback-Leibler (KL) divergence in information theory or the Itakura-Saito distance in speech processing—are Bregman divergences. These measures are not metrics; they are often asymmetric ($D(x, y) \neq D(y, x)$) and violate the triangle inequality. Consequently, standard search algorithms fail, often forcing a choice between slow exhaustive searches or heuristics without theoretical guarantees.
Geometric Foundations: Beyond the Triangle Inequality
To bridge this gap, the authors identify two "relaxed" geometric properties that Bregman divergences possess, which are sufficient to support efficient searching:
- Reverse Triangle Inequality (RTI): Intuitively, along a line, the sum of two contiguous segments is less than the length of the union.
- $\mu$-defectiveness: This is a relaxation of the triangle inequality where the "error" in the distance relationship is bounded by a constant factor $\mu$.
A key technical insight is the Square Root Transformation. While a Bregman divergence itself is not $\mu$-defective, its square root often is. By performing searches in this transformed space, the authors regain the geometric control necessary for spatial decomposition.
Methods: The Ring-Tree + Quad-Tree Paradigm
The paper adapts a two-stage search strategy to these non-metric spaces:
- Ring-Tree: This structure provides a rough initial approximation to prune the search space significantly.
- Quad-Tree: A recursive spatial decomposition (similar to bisection) is then used to zoom in on the exact $(1+\epsilon)$ approximate neighbor.
The research proposes two distinct algorithms. The first is a general-purpose algorithm for any $\mu$-defective measure. The second is optimized specifically for Bregman divergences by utilizing a structural parameter ($c_0$) related to the maximum ratio of the function's second derivatives over the search domain.
Key Results and Complexity
The paper achieves two major complexity milestones for $(1+\epsilon)$-Approximate Nearest Neighbor (ANN) search:
- Algorithm 1 (General): Resolves queries in $O((\frac{\mu \log n}{\epsilon})^{O(d)})$ time using $O(n \log^{d-1} n)$ space.
- Algorithm 2 (Bregman-Specific): Achieves a much faster $O(\log n)$ query time and $O(n)$ space, though the query time constant includes a factor of $(c_0)^d$.
This effectively moves Bregman near-neighbor search from the realm of "prohibitively expensive" to "asymptotically as fast as Euclidean search" for fixed dimensions.
Limitations and Future Work
While these algorithms provide a theoretical breakthrough, they face the curse of dimensionality, as complexity is exponential in the number of dimensions ($d$). They are best suited for low-to-medium dimensional data. Furthermore, the efficiency is tied to the "boundedness" of the domain; if data ranges from zero to infinity, the constants $\mu$ and $c_0$ can grow significantly. Future work may explore whether sublinear search is possible without any dependence on $\mu$-defectiveness or more robust "intrinsic" geometric bisection methods.
Summary updated