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

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

2011-08-03

arxiv.org/abs/1108.0835v5

Computer Science

Computational Geometry

29 pages, including appendices and bibliography. Accepted at SOCG 2012

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Approximate Bregman near neighbors in sublinear time: Beyond the triangle inequality does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximate Bregman near neighbors in sublinear time: Beyond the triangle inequality, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximate Bregman near neighbors in sublinear time: Beyond the triangle inequality will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-664092