[Insight-users] Hashing 3D euclidean vectors?

[motes motes]

On Sun, Nov 29, 2009 at 5:52 AM, Karthik Krishnan
<karthik.krishnan at kitware.com> wrote:
> A hash table is probably not the way to go there. I've never heard of
> anyone doing that, it may not be possible either to design a well
> dimensioned hash table to achieve this in amortized time.

Maybe I am misunderstanding you but I am pretty sure that 'spatial
hashing' using hash-tables are a well known technique. Here are just a
few of the resource I found when googling Locality-Sensitive Hashing:

http://en.wikipedia.org/wiki/Locality_sensitive_hashing
http://www.mit.edu/~andoni/LSH/
http://people.csail.mit.edu/indyk/nips-nn.ps




>
> What you might want to look at is the locator framework in VTK. These
> divide the search space into buckets based on various strategies and
> you can search pretty efficiently for the closest neighbors. See
>
>  vtkPointLocator::FindClosestPoint

Thanks, I will check it out!

>
> You mention below that these are regular spaced points.. Are the
> points stored in memory in some sort of adjacency. Search for closest
> points woul dbe trivial then

Currently I just store them in a std::map which I then move to the
hash-table using a Locality-Sensitive hash-function (to be
implemented).



>
> On Sat, Nov 28, 2009 at 9:38 PM, motes motes <mort.motes at gmail.com> wrote:
>> I need to hash regular spaced points located in 3D such that points
>> that are close to each other hash to the same value (gets stored in
>> the same chain) and points that are far from each other hash to
>> different values (are stored in different chains). This way I can
>> given a random point find the chain with the closest neighbors in
>> constant time.
>>
>> Can someone recommend a good hash function that does the above?
>> _____________________________________
>> Powered by www.kitware.com
>>
>> Visit other Kitware open-source projects at
>> http://www.kitware.com/opensource/opensource.html
>>
>> Kitware offers ITK Training Courses, for more information visit:
>> http://www.kitware.com/products/protraining.html
>>
>> Please keep messages on-topic and check the ITK FAQ at:
>> http://www.itk.org/Wiki/ITK_FAQ
>>
>> Follow this link to subscribe/unsubscribe:
>> http://www.itk.org/mailman/listinfo/insight-users
>>
>