Exclusive grouped spatial hashing. (February 2018)

• Record Type: Journal Article
• Authors: Duan, Weiwei; Luo, Jianxin; Ni, Guiqiang; Tang, Bin; Hu, Qi; Gao, Yi
• Is Part Of: Computers & graphics. Volume 70(2018)
• Page Start: 71
• Page End: 79
• Publication Date: 2018-02
• Subjects: Exclusive grouped hashing -- Multidimensional hashing -- Spatial data -- Repetitive data; Computer graphics -- Periodicals; 006.6
• DOI: 10.1016/j.cag.2017.08.012
• Languages: English
• ISSNs: 0097-8493

Abstract

Highlights: An exclusive grouped spatial hashing scheme for compression of repetitive data in multidimensional domains is proposed. By making full use of hashing collisions, each entry of the hash tables replaces a group of repetitive elements. The method retains efficient random access on GPUs without any losses. Graphical abstract: Frame of exclusive grouped hashing algorithm. In each level, repetitive elements of the input domain are compressed into a tiny hash table. The uncompressed data are forward to indirect domain, which is treated as a new input domain for next level. The coverage table is used to mark the corresponding level of iteration for compressed data. Abstract: A novel multidimensional hashing scheme, named the Exclusive Grouped Spatial Hashing (EGSH), which compresses repetitive spatial data into several compact tables while retaining efficient random access, is presented. EGSH represents a multi-level hashing without any losses. Moreover, EGSH compresses a group of repetitive elements into the same entry of the hash tables, while it uses a coverage table to mark the corresponding hash tables of the compressed data. Although, prior hashing work is related to hash collisions mitigation, here a full use of these collisions is obtained and therefore the spatial data compression rate is improved. The performance of exclusive grouped spatial hashing is presented in 2D and 3D graphic examples.