Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is my first post on the mathematics stack exchange site. If I am posting this question on the wrong site, I apologize and please let me know so I can delete it.

I am a programmer, and one thing we have to worry about is optimization. This is why my question probably isn't as simple as it seems: given a point (i.e point A) in an N-dimensional space, find the closest point to that point (i. e. in a set of points B-Z in 5-dimensions).

Now the obvious solution is to find the euclidean distance from the given point to every other point and take the minimum, but this can be extremely inefficient if I am working with a large set of points (I am talking maybe a billion or so). Memory should not be a problem, I am just worried about speed.

One untested, simple idea I had on this was to create an N amount of lists. The Nth list will be sorted by the nth dimension. I can then take my given point of 5-dimension, lets make it (3, 9, 1, 0, 2). I will go through each sorted array, starting at where x1 = 3 in the first array, and then where x2 = 9 in the second array, etc. and spread out until a certain predetermined point so that I won't have to go through all of the points.

I am not to sure if that method made sense, but even if it didn't, is there another way of going about this?

Thank you!

share|improve this question
4  
    
Grr. I wasn't too sure exactly what to search for to get an article like that, but that actually addresses exactly what I was looking for. If any one has any solution from there, or any other solution otherwise, to suggest, please let met know. Thank you so much for that comment Qiaochu! –  mathguy Aug 2 '12 at 4:38

1 Answer 1

up vote 1 down vote accepted

So after testing, I learned that my method was completely naive and futile.

@Qiaochu Yuan, I looked at your link, and I learned that a VP-tree may be the way to go for me. It seems easy to implement and it also seems very reliable.

For anyone that is wondering, this is how the VP-tree works: Of course the important step is indexing the data correctly, it is just the search that needs to be fast. To index the data 1. Pick a random point from the set of points. 2. Start building a tree, with the top node containing all data. 3. Find the distance from that point to all other points in the set. 4. The left child contains nodes that are within the median distance of all the nodes. The right child contains the rest of the nodes. 5. Repeat 3-5 for each of the partitions until data points have run out.

Now searching is easy, just like a normal binary search I guess. 1. Add the search node to the space of terms. 2. Start by searching the root node. 3. Find the closest child, and search that. 4. Keep repeating 3 until necessary.

I am basing this information out of http://stevehanov.ca/blog/index.php?id=130, but I still especially want to thank Qiaochu.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.