On Tue, May 02, 2017 at 12:22:37AM +0530, Ankit Aggarwal wrote: > Hi Ryan > > I was going through the "Tree independent Dual tree Algorithm" paper(wrote > by you) which talks about the some of the algorithms. > > Can you explain how does the tight upper bound of k-nearest neighbor work > intuitively? > > "The basic problem is: given a set of points and integer k, choose k points > that minimize the maximum distance between a point in the set and its > nearest neighbor in the set" > > How are you thinking to extend it to Dual tree algorithms?
Hi Ankit, The upper bounds that are used in dual-tree nearest neighbor search are fairly straightforward extensions of the triangle inequality. The bounds are simply bounds on the furthest possible distance between a query point and its k-nearest neighbor. If you'd like further clarification, you can consult the references of the paper or you can also read my Ph.D. thesis for a longer version. For developing the k-centers algorithm, the idea will center around determining when you can prune a point from a particular set. Realistically I would say that if you are not 100% familiar with dual-tree algorithms, it would be very difficult to quickly come up with a solution to this problem. Thanks, Ryan -- Ryan Curtin | "I'm just going to shoot you once!" [email protected] | - Joseph Dunn _______________________________________________ mlpack mailing list [email protected] http://knife.lugatgt.org/cgi-bin/mailman/listinfo/mlpack
