[Insight-users] Hashing 3D euclidean vectors?

[Luis Ibanez]

Hi Motes,

an ITK Point locator implementation is available
in the NAMIC Sandbox at:

QuadEdgeMeshRigidRegistration/Source
                                         itkPointLocator2.h
                                         itkPointLocator2.txx

http://svn.na-mic.org/NAMICSandBox/trunk/QuadEdgeMeshRigidRegistration/Source/


     Regards,


             Luis


--------------------------------------------------------------------------------------------
On Sun, Nov 29, 2009 at 6:13 AM, motes motes <mort.motes at gmail.com> wrote:
> 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
>>>
>>
> _____________________________________
> 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
>