|
|
|
| Title | Real-Time Parallel Hashing on the GPU
(Article) |
|---|
| in | ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH Asia 2009) |
|---|
|
| Author(s) |
Dan A. Alcantara, Andri Sharf, Fatemeh Abbasinejad, Shubhabrata Sengupta, Michael Mitzenmacher, John D. Owens, Nina Amenta |
|---|
|
| Year |
December 2009
|
|---|
| Location | Yokohama, Japan |
|---|
| Date | December 2009 |
|---|
| Volume | 28 |
|---|
| Number | 5 |
|---|
|
| URL | http://idav.ucdavis.edu/~dfalcant/research/hashing.php |
|---|
|
| Download |  |
|---|
|
| BibTeX |  |
|---|
|
| Abstract |
We demonstrate an efficient data-parallel algorithm for building
large hash tables of millions of elements in real-time. We consider
two parallel algorithms for the construction: a classical sparse perfect
hashing approach, and cuckoo hashing, which packs elements
densely by allowing an element to be stored in one of multiple possible
locations. Our construction is a hybrid approach that uses both
algorithms. We measure the construction time, access time, and
memory usage of our implementations and demonstrate real-time
performance on large datasets: for 5 million key-value pairs, we
construct a hash table in 35.7 ms using 1.42 times as much memory
as the input data itself, and we can access all the elements in
that hash table in 15.3 ms. For comparison, sorting the same data
requires 36.6 ms, but accessing all the elements via binary search
requires 79.5 ms. Furthermore, we show how our hashing methods
can be applied to two graphics applications: 3D surface intersection
for moving data and geometric hashing for image matching.
|
|---|
|
|
| Note |
To appear
|
|---|
|
