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

Amirali Abdullah, John Moeller, Suresh Venkatasubramanian

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(…