Approximate Bregman Near Neighbors in Sublinear time: Beyond the triangle inequality

摘要

In this paper, we give the first provably approximate nearest neighbor (ANN) algorithms for Bregman divergences over bounded domain. These process queries in O(log n) time for fixed dimensions. We also obtain poly-log n bounds for a more abstract class of distance measures (containing Bregman divergences) which satisfy certain structural properties. Both of these bounds apply to the regular asymmetric Bregman divergences as well as their symmetrized versions. Our first algorithm resolves a query for a d-dimensional (1 + ε) ANN in O (((log n)/ε)~(O(d))) time and O (n log~(d-1) n) space and holds for generic μ-defective distance measures satisfying a reverse triangle inequality. Our second algorithm is more specific in analysis to the Bregman divergences and uses a further structural constant, the maximum ratio of second derivatives over each dimension of our domain (c_0). This allows us to locate a (1 + ε)-ANN in O(log n) time and O(n) space, where there is a further (c_0)~d' factor in the big-Oh for the query time.