Ismael García
Abstract
Recent spatial hashing schemes hash millions of keys in parallel, compacting sparse spatial data in small hash tables while still allowing for fast access from the GPU. Unfortunately, available schemes suffer from two drawbacks: Multiple runs of the construction process are often required before success, and the random nature of the hash functions decreases access performance.
We introduce a new parallel hashing scheme which reaches high load factor with a very low failure rate. In addition our scheme has the unique advantage to exploit coherence in the data and the access patterns for faster performance. Compared to existing approaches, it exhibits much greater locality of memory accesses and consistent execution paths within groups of threads. This is especially well suited to Computer Graphics applications, where spatial coherence is common. In absence of coherence our scheme performs similarly to previous methods, but does not suffer from construction failures.
Our scheme is based on the Robin Hood scheme modified to quickly abort queries of keys that are not in the table, and to preserve coherence. We demonstrate our scheme on a variety of data sets. We analyze construction and access performance, as well as cache and threads behavior.
- Alcantara, D. A., Sharf, A., Abbasinejad, F., Sengupta, S., Mitzenmacher, M., Owens, J. D., and Amenta, N. 2009. Real-time parallel hashing on the GPU. ACM Transactions on Graphics (Proc. ACM SIGGRAPH Asia) 28, 5. Google Scholar
Digital Library
- Alcantara, D. A., Volkov, V., Sengupta, S., Mitzenmacher, M., Owens, J. D., and Amenta, N. 2011. Building an efficient hash table on the GPU. In GPU Computing Gems, W.-m. W. Hwu, Ed., vol. 2. Morgan Kaufmann, ch. 1.Google Scholar
- Botelho, F. C., and Ziviani, N. 2007. External perfect hashing for very large key sets. In Proceedings of the sixteenth ACM Conference on Conference on Information and Knowledge Management, ACM, CIKM '07, 653--662. Google ScholarDigital Library
- Celis, P. 1986. Robin Hood Hashing. PhD thesis, University of Waterloo, Ontario, Canada. Google ScholarDigital Library
- Devroye, L., Morin, P., and Viola, A. 2004. On worst-case robin hood hashing. SIAM Journal on Computing 33, 923--936.Google ScholarCross Ref
- Lefebvre, S., and Hoppe, H. 2006. Perfect spatial hashing. ACM Transactions on Graphics (Proc. ACM SIGGRAPH) 25, 3, 579--588. Google ScholarDigital Library
- Linial, N., and Sasson, O. 1996. Non-expansive hashing. In Proceedings of the twenty-eighth annual ACM Symposium on Theory of Computing, ACM, STOC '96, 509--518. Google ScholarDigital Library
- Pagh, R., and Rodler, F. F. 2004. Cuckoo hashing. Journal of Algorithms 51, 2, 122--144. Google ScholarDigital Library
- Peterson, W. W. 1957. Addressing for random-access storage. IBM Journal of Research and Development 1, 2, 130--146. Google ScholarDigital Library
Index Terms
- Coherent parallel hashing
Recommendations
Coherent parallel hashing
SA '11: Proceedings of the 2011 SIGGRAPH Asia ConferenceRecent spatial hashing schemes hash millions of keys in parallel, compacting sparse spatial data in small hash tables while still allowing for fast access from the GPU. Unfortunately, available schemes suffer from two drawbacks: Multiple runs of the ...
Extendible hashing—a fast access method for dynamic files
Extendible hashing is a new access technique, in which the user is guaranteed no more than two page faults to locate the data associated with a given unique identifier, or key. Unlike conventional hashing, extendible hashing has a dynamic structure that ...
Complementary Projection Hashing
ICCV '13: Proceedings of the 2013 IEEE International Conference on Computer VisionRecently, hashing techniques have been widely applied to solve the approximate nearest neighbors search problem in many vision applications. Generally, these hashing approaches generate 2^c buckets, where c is the length of the hash code. A good hashing ...
Comments