High-Dimensional Spaces Are Counterintuitive, Part Five

All 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 being junk. The idea that these smart Microsoft researchers came…

3

High-Dimensional Spaces Are Counterintuitive, Part Four

It’s reasonably common to have a database containing a few thousand or million points in some high-dimensional space.  If you have some “query point” in that space you might like to know whether there is a match in your database.   If you’re looking for an exact match then the problem is pretty easy — you…

5

High-Dimensional Spaces Are Counterintuitive, Part Three

My next book project is ready for copyediting, the wedding invitations are sent out, my bug count is under control, I’ve got a layer of levelling compound poured in the basement, there’s no more ivy on my roof, and I’m rigging my sailboat some time this week (about six weeks later than I would have…

6

High-Dimensional Spaces Are Counterintuitive, Part Two

The volume of an n-cube of edge length s is easy to work out. A 2-cube has s2 units of area. A 3-cube has s3 units of volume. A 4-cube has s4 units of 4-volume, and so on — an n-cube has sn units of n-volume. If the n-cube has edge of s>1, say s=2,…

2

High-Dimensional Spaces Are Counterintuitive, Part One

A friend of mine over in Microsoft Research pointed out to me the other day that high-dimensional spaces are really counterintuitive.  He’d just attended a lecture by the research guys who wrote this excellent paper and we were geeking out at a party about it.  I found this paper quite eye-opening and I thought I might…

11