Some hashing research

A kdtree

hi guys!

These days I’m busy researching on spatial hashing, is a deep and wide field.
currently particles are using a very efficient and general purpose kdtree structure. A kdtree is basically a hieraquical data structure to make fast queries of nearest neighbours of a given point in space, in other words is a space partitioning data structure.
Well, near every tree type structure have worst cases of O(nlogn) for query, inserting and so on, the cool thing about hashing is that they have O(1) insertion time and linear seeking time (is not so simple but to keep the explanation for all audiences 🙂 ) , the main drawbak of hashing structures are choosing the hash function, it have the biggest impact on the performance of the algorithm. hashing basically subdivides the entire space in an infinite array of buckets, and storing only the buckets that contains objects (particles) , so the buckets size is the second factor that influence the hash performance.
In my experiemnts I have situations where is faster than kdtree and others where is slower that’s why I’m searching for an efficient and simple hash function and to be able to correctly handling hash collisions (the effect where different particles in distant space positions are mapped to the same bucket)

Hasing, if well implemented, could show advantage over kdtree on large and sparse particle counts.

Cheers   Farsthary

Advertisements
Some hashing research

8 thoughts on “Some hashing research

  1. guillaume says:

    By O(nlogn) for query or insertion, what do you mean exacly ?

    Because a well balanced binary tree have a query computation cost of O(logn), If yours is O(nlogn), I suggest you to replace it by a basic vector, which have query and insert in (WORST) O(n) 😉

    Like

  2. farsthary says:

    @guillaume

    Because all particles need to be queried, then it will be proportional to O(nlogn) , a single particle/query is indeed O(logn) , using a basic vector would be then O(nn) that is the worst case 😉

    Like

  3. blenderificus says:

    well, this is certainly some complex material. Congrats on delving into such an interesting area of 3d coding, perhaps the blender world community will benefit one day from your new adventure 😉

    Thank you Farsthary

    Like

  4. kmilo says:

    Saludos
    Raul es camilo de la UCI tengo una duda hermano y no se donde mas preguntar tienes alguna idea de como puedo poner un driver a la visulizacion de un objeto.Por cierto buen trabajo con las particulas estoy ansioso de verlas generando superficie.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s