2

I found lot's of discussions and articles that there is possible to find approximate nearest neighbours using Locality Sensitive Hashing (LSH) in 3d spatial coordinates. Unfortunately I was unable to find any real working example, where everything could be done in single copy-paste code.

I am using C# (more specifically Unity) and noticed that some articles stating that approximate NNS can be fast approach for game development. However, I didn't found any real C# implementations yet (or maybe C++ if C# does not exist).

So does anybody know some possible solutions for this?

gsamaras
  • 71,951
  • 46
  • 188
  • 305
chanfort
  • 125
  • 1
  • 1
  • 9

1 Answers1

1

Why use LSH in 3 dimensions? I would suggest you try some tree-based approach, like KD-trees (there are many options). Here is a C# question about KD trees. You could check ALGLIB for KD-trees.

Notice that depending on your dataset, the choice of the data structure differs. You can take a look about some comparisons I had made (in higher dimensions though) here and here.

You can check this link LSH for Finding Similar Documents from a large number of Documents in C# in order to get a C# taste. An interesting question is here.

If you insist on LSH, then since you are dealing with game development, C++ could be also a choice maybe, so here is E2LSH library.

EDIT

ANN has to do with approximate NNS. It uses KD trees and BBD trees. You can check some answers of mine for ANNS here.

Community
  • 1
  • 1
gsamaras
  • 71,951
  • 46
  • 188
  • 305
  • Hi Samaras, thanks for message. In [this](http://stackoverflow.com/questions/4350215/fastest-nearest-neighbor-algorithm) thread I found that [ANN](http://www.cs.umd.edu/~mount/ANN/) can be significantly faster than kdtrees just from the account that I would be getting approximate neighbour. This would be exactly what I am interested, as kdtrees for me does not show enough performance and in games it's acceptable to have "approximate" neighbours. – chanfort Jan 20 '15 at 18:34
  • P.S. I was interested about C++, as I may try to rewrite it to C# if it is not implemented yet... – chanfort Jan 20 '15 at 18:36
  • I didn't know you wanted ANN! Is the answer OK for you or should I delete it? – gsamaras Jan 20 '15 at 18:40
  • Answer looks ok, you can keep it. But when talking about question, I am curious about these ANN algorithms and if there isn't some algorithms already written in C#, so I could save a lot of time instead of rewriting and reimplementing things from C++. P.S. I am not yet sure if ANN would be the best, as it was made 4 years ago and lots of things could be changed during this time. – chanfort Jan 20 '15 at 18:47