Abstract:

In order to use an extended hash table for fast data accessing ， an efficient index updating to maintain the hash table is necessary. Proposed in this his paper is a GPU-based extendible hashing algorithm named gEHT ， which takes full advantage of GPU ’ s parallel computing power ， and adopts list reuse as well as pre-split technology to extend and merge lists and to insert and delete data in a lock-free manner. Thus ， high levels of concurrency for hash table creation ， index updating and data retrieval are realized. Experimental results show that gEHT is superior to some other linear hashing and extendible hashing algorithms on the basis of multi-core CPU in terms of querying data ， maintaining hash table and updating index ， especially in the case of heavy load.

Key words: extendible hashing, parallel computing, GPU, algorithm, multi-core CPU