undefined | Better HN

0 pointsamrx4316y ago0 comments

Few questions:

1. Where can I find that algorithm you are talking about?

2. The algorithm which you stated seems a bit complex from the algos taught in the undergrad level, so what are the pre-requisites for understanding it that I must be aware of?

3. What books or papers you would suggest for reading?

4. How the hell you remember something you read decades ago :)?

0 comments

pfdietz6y ago

The ML problem involved, for a set of points on a line, computing the sum (over all the pairs of distinct points) of a function d(x_i,x_j) that is, in some sense, well behaved. The purpose was to compute the similarity of two sets of real numbers.

It turns out this can be done (to sufficient accuracy) in nearly linear time using something called the fast multipole method.

http://www.umiacs.umd.edu/labs/cvl/pirl/vikas/publications/F...

I wouldn't consider the "O(log n) chunks" trick all that complex, btw, although Tarjan did have to point it out to me when I should have used it.

amrx431OP6y ago

> Tarjan did have to point it out to me when I should have used it.

Wow, you worked with Tarjan. How cool!!!.

pfdietz6y ago

Not directly, but he did point out the improvement.

j / k navigate · click thread line to collapse

0 comments

pfdietz6y ago

It turns out this can be done (to sufficient accuracy) in nearly linear time using something called the fast multipole method.

http://www.umiacs.umd.edu/labs/cvl/pirl/vikas/publications/F...

I wouldn't consider the "O(log n) chunks" trick all that complex, btw, although Tarjan did have to point it out to me when I should have used it.

amrx431OP6y ago

> Tarjan did have to point it out to me when I should have used it.

Wow, you worked with Tarjan. How cool!!!.

pfdietz6y ago

Not directly, but he did point out the improvement.

j / k navigate · click thread line to collapse