[Scilab-users] Pairwise distance of a huge amount of points

[shorne at energetiq.com]

Jumping in late -- 
If your goal is to find nearest the N neighbors of a given point, look up 
the K-D Tree algorithm --( I used it some decades ago...  in my case the 
points were each of higher dimension -- around 9 or so.)

And if that is the application, and you want to go fast - consider using 
something other than the L-2 norm to set up the tree.  L-1 should be much 
faster - sum of absolute values of component distances; no squaring or 
square roots -- "Manhattan norm"
Once you have built the tree and retrieved a bunch of nearest neighbors, 
you can of course compute the L-2 distances over that much smaller set, if 
necessary...

S





From:
"Dang, Christophe" <Christophe.Dang at sidel.com>
To:
"International users mailing list for Scilab." <users at lists.scilab.org>, 
Date:
08/29/2014 06:58 AM
Subject:
Re: [Scilab-users] Pairwise distance of a huge amount of points
Sent by:
"users" <users-bounces at lists.scilab.org>



Just to close the subject:

I tried to implement the algorithm with sparse matrices, and it is less 
efficient than scanning over one dimension: 7 times faster than the naive 
algorithm.

If I generate the sparse matrix from a n*(n-1)/2 vector,
it is even worse: less efficient than the naive algorithm (1.1 times 
longer),
this only to gain a factor 2 on the amount of points that can be handeled.

Conclusion: forget the sparse matrices for this application.

--
Christophe Dang Ngoc Chan
Mechanical calculation engineer

______________________________________________________________________

This e-mail may contain confidential and/or privileged information. If you 
are not the intended recipient (or have received this e-mail in error), 
please notify the sender immediately and destroy this e-mail. Any 
unauthorized copying, disclosure or distribution of the material in this 
e-mail is strictly forbidden.
______________________________________________________________________
_______________________________________________
users mailing list
users at lists.scilab.org
http://cp.mcafee.com/d/1jWVIe418SyNsQsITd79EVpKrKrsKDtCXUUSVteXaaapJOWtSrLL6T4S7bLzC3t2toMY5v3UAvD8mVsTYfyh-sxrBPrTSvLtx_HYCCyyyyqeuLsKyqerTVBdV4sMZORQr8EGTsjVkffGhBrwqrhdECXYCej79zANOoUTsS03fBiteFqh-Ae00U9GX33VkDa3JsrFYq6SWv6xsxlK5LE2zVkDjGmAvF3w09JZdNcS2_id41Fr6bifQwnrFYq6BQQg1rphciFVEwgBiuMJVEwGWq8dd41dIzVEwRmHs9Cy2HFEwmHa4W6T6jp-xPMhmc


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.scilab.org/pipermail/users/attachments/20140829/d4c19dbc/attachment.htm>