High-Dimensional Spaces Are Counterintuitive, Part Fivehttp://blogs.msdn.com/b/ericlippert/archive/2005/06/20/high-dimensional-spaces-are-counterintuitive-part-five.aspxAll of this stuff about high dimensional geometry has been known for quite a while. The novel bit that this paper is all about is how to actually build a fast index for searching a high-dimensional space where the query has a strong likelihood of beingen-USTelligent Evolution Platform Developer Build (Build: 5.6.50428.7875)re: High-Dimensional Spaces Are Counterintuitive, Part Fivehttp://blogs.msdn.com/b/ericlippert/archive/2005/06/20/high-dimensional-spaces-are-counterintuitive-part-five.aspx#8945462Thu, 11 Sep 2008 23:49:17 GMT91d46819-8472-40ad-a661-2c78acb4018c:8945462Brad Dodson<p>This is an interesting idea. Personally I've written a nearest-neighbor search system based on approximate k-d tree search called "Best Bin First" from a paper by David Lowe. It'd be interesting to know how they compare. It may actually worthwhile for me to implement this algorithm (or perhaps LSH) for the system I was doing (it was comparing scale-invariant features in images), since junk queries were definitely a problem for me (once the nearest neighbor is far enough away, I don't really care anymore, even though these queries are the ones taking the longest most of the time).</p>
<p>Thanks for the great article!</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=8945462" width="1" height="1">re: High-Dimensional Spaces Are Counterintuitive, Part Fivehttp://blogs.msdn.com/b/ericlippert/archive/2005/06/20/high-dimensional-spaces-are-counterintuitive-part-five.aspx#430947Tue, 21 Jun 2005 05:28:20 GMT91d46819-8472-40ad-a661-2c78acb4018c:430947Eric W. BachtalThanks for the series. It was mostly a head scratching exercise for me, but enjoyable nonetheless. In the spirit of searching millions of data points, I thought you might enjoy this:
<br>
<br><a rel="nofollow" target="_new" href="http://www.princeton.edu/artofscience/gallery/view.php%3Fid=40.html">http://www.princeton.edu/artofscience/gallery/view.php%3Fid=40.html</a>
<br>
<br>"This graphic comes from a dynamic asset allocation problem in railroads. The system, which is now in production at Norfolk Southern railroad, is the first production implementation of a stochastic, dynamic programming model in freight transportation. The model is based on the Ph.D. dissertation of Huseyin Topaloglu (now a professor at Cornell University) for stochastic, integer multicommodity flow problems. The original research was modified to handle multidimensional attribute problems, with millions of asset types."<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=430947" width="1" height="1">re: High-Dimensional Spaces Are Counterintuitive, Part Fivehttp://blogs.msdn.com/b/ericlippert/archive/2005/06/20/high-dimensional-spaces-are-counterintuitive-part-five.aspx#430904Tue, 21 Jun 2005 01:49:50 GMT91d46819-8472-40ad-a661-2c78acb4018c:430904foxyshadisScripting question: When does JScript get hyperdimensional math language constructs? ;)<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=430904" width="1" height="1">