tag:blogger.com,1999:blog-6555947.post113786791721785010..comments2024-03-14T01:32:43.610-06:00Comments on The Geomblog: SODA report: ALENEX...Suresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-6555947.post-1138055575712409772006-01-23T15:32:00.000-07:002006-01-23T15:32:00.000-07:00Hi, A few more points:- from my experience, kd-tr...Hi,<BR/><BR/> A few more points:<BR/><BR/>- from my experience, kd-trees and related techniques are doing <EM>surprisingly</EM> well even in high dimensions, if you use those algorithms "beyond" the provable bounds. E.g., you can stop the search after a fixed number of steps, or you can set the approximation factor to a very high value. Amazingly, the <EM>actual</EM> points reported are often of pretty good quality (e.g., you get the actual nearest neighbor 50% the time). Of course, no guarantees, but in many applications you can live without them.<BR/><BR/>- there are techniques that one can use if your data is nominally high-dimensional, but "really" the points live on a "low-dimensional manifold". See the following <A HREF="http://cm.bell-labs.com/who/clarkson/nn_survey/p.pdf" REL="nofollow"> survey</A>  for more info. <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A><A HREF="http://geomblog.blogspot.com/2006/01/soda-report-alenex.html#comments" REL="nofollow" TITLE="indyk at mit dot edu">Piotr</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1137969506652662232006-01-22T15:38:00.000-07:002006-01-22T15:38:00.000-07:00Ken: well I paraphrased, but that is basically wh...Ken:<BR/> well I paraphrased, but that is basically what he said :). Essentially he argued that it's the most successful technique, but he did point out that LSH doesn't exist for all metrics, and even important metrics like the edit distance. <BR/><BR/>Ingo: a good starting point is the web page at <BR/>http://web.mit.edu/andoni/www/LSH/index.html <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>SureshSuresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1137961531097548002006-01-22T13:25:00.000-07:002006-01-22T13:25:00.000-07:00I'd love to learn more about locality-sensitive ha...I'd love to learn more about locality-sensitive hashing! My exposition to hashing was from cryptography, which is the anti-thesis of locality sensitivity ;-) Did David mention anything in particular that would be good introductory reading? What is state-of-the-art there? <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A><A HREF="http://geomblog.blogspot.com/2006/01/soda-report-alenex.html" REL="nofollow" TITLE="iluetkeb at gmail dot com">Ingo</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1137879445809308782006-01-21T14:37:00.000-07:002006-01-21T14:37:00.000-07:00I'm sorry I missed David's talk.-kd-trees are even...I'm sorry I missed David's talk.<BR/><BR/>-kd-trees are even better, if you want the best bounds<BR/><BR/>You mean "performance" here, right? I'd pretty much agree in that case, for low enough dimension.<BR/><BR/>-In high dimensions, only locality sensitive hashing can save us.<BR/><BR/>Well, there are some other techniques that are sometimes helpful. Surely there's nothing that's *always* helpful, is there? <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A><A HREF="http://geomblog.blogspot.com/2006/01/soda-report-alenex.html#comments" REL="nofollow" TITLE="clarkson at lucent dot com">Ken Clarkson</A>Anonymousnoreply@blogger.com