<font size=2 face="sans-serif">Jumping in late -- </font>
<br><font size=2 face="sans-serif">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.)</font>
<br>
<br><font size=2 face="sans-serif">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"</font>
<br><font size=2 face="sans-serif">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...</font>
<br>
<br><font size=2 face="sans-serif">S</font>
<br>
<br>
<br>
<br>
<br>
<table width=100%>
<tr valign=top>
<td><font size=1 color=#5f5f5f face="sans-serif">From:</font>
<td><font size=1 face="sans-serif">"Dang, Christophe" <Christophe.Dang@sidel.com></font>
<tr valign=top>
<td><font size=1 color=#5f5f5f face="sans-serif">To:</font>
<td><font size=1 face="sans-serif">"International users mailing list
for Scilab." <users@lists.scilab.org>, </font>
<tr valign=top>
<td><font size=1 color=#5f5f5f face="sans-serif">Date:</font>
<td><font size=1 face="sans-serif">08/29/2014 06:58 AM</font>
<tr valign=top>
<td><font size=1 color=#5f5f5f face="sans-serif">Subject:</font>
<td><font size=1 face="sans-serif">Re: [Scilab-users] Pairwise distance
of a huge amount of points</font>
<tr valign=top>
<td><font size=1 color=#5f5f5f face="sans-serif">Sent by:</font>
<td><font size=1 face="sans-serif">"users" <users-bounces@lists.scilab.org></font></table>
<br>
<hr noshade>
<br>
<br>
<br><tt><font size=2>Just to close the subject:<br>
<br>
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.<br>
<br>
If I generate the sparse matrix from a n*(n-1)/2 vector,<br>
it is even worse: less efficient than the naive algorithm (1.1 times longer),<br>
this only to gain a factor 2 on the amount of points that can be handeled.<br>
<br>
Conclusion: forget the sparse matrices for this application.<br>
<br>
--<br>
Christophe Dang Ngoc Chan<br>
Mechanical calculation engineer<br>
<br>
______________________________________________________________________<br>
<br>
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.<br>
______________________________________________________________________<br>
_______________________________________________<br>
users mailing list<br>
users@lists.scilab.org<br>
</font></tt><a href="http://cp.mcafee.com/d/1jWVIe418SyNsQsITd79EVpKrKrsKDtCXUUSVteXaaapJOWtSrLL6T4S7bLzC3t2toMY5v3UAvD8mVsTYfyh-sxrBPrTSvLtx_HYCCyyyyqeuLsKyqerTVBdV4sMZORQr8EGTsjVkffGhBrwqrhdECXYCej79zANOoUTsS03fBiteFqh-Ae00U9GX33VkDa3JsrFYq6SWv6xsxlK5LE2zVkDjGmAvF3w09JZdNcS2_id41Fr6bifQwnrFYq6BQQg1rphciFVEwgBiuMJVEwGWq8dd41dIzVEwRmHs9Cy2HFEwmHa4W6T6jp-xPMhmc"><tt><font size=2>http://cp.mcafee.com/d/1jWVIe418SyNsQsITd79EVpKrKrsKDtCXUUSVteXaaapJOWtSrLL6T4S7bLzC3t2toMY5v3UAvD8mVsTYfyh-sxrBPrTSvLtx_HYCCyyyyqeuLsKyqerTVBdV4sMZORQr8EGTsjVkffGhBrwqrhdECXYCej79zANOoUTsS03fBiteFqh-Ae00U9GX33VkDa3JsrFYq6SWv6xsxlK5LE2zVkDjGmAvF3w09JZdNcS2_id41Fr6bifQwnrFYq6BQQg1rphciFVEwgBiuMJVEwGWq8dd41dIzVEwRmHs9Cy2HFEwmHa4W6T6jp-xPMhmc</font></tt></a><tt><font size=2><br>
</font></tt>
<br>