Approximate Bregman near neighbors in sublinear time: Beyond the triangle inequality

Amirali Abdullah, John Moeller, Suresh Venkatasubramanian

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.

Table 1: Common Bregman divergences and their associated potential functions $\phi$ and distance measures $D_\phi$.

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:

  1. Reverse Triangle Inequality (RTI): Intuitively, along a line, the sum of two contiguous segments is less than the length of the union.
  2. $\mu$-defectiveness: This is a relaxation of the triangle inequality where the "error" in the distance relationship is bounded by a constant factor $\mu$.
Figure 1: Visualizing $\mu$-defectiveness, where the ratio of distances between a query $q$, its nearest neighbor $nn_q$, and a candidate point $cand$ is bounded.

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

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.
BibTeX
@article{abdullah2013approximate,
  author = {Amirali Abdullah and John Moeller and Suresh Venkatasubramanian},
  title = {{Approximate Bregman near neighbors in sublinear time: Beyond the triangle inequality}},
  journal = {Int. J. Comput. Geom. Appl.},
  year = {2013},
  url = {https://openreview.net/forum?id=khD4L0e1S1},
}
Figure