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

Abstract:In this paper we present the first provably 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 The nearest neighbor problem is one of the most extensively studied problems in data analysis. The past 20 years has seen tremendous research into the problem of computing near neighbors efficiently as well as approximately in different kinds of metric spaces. 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.