A SUBSTRING SEARCH ALGORITHM IN EXTENDIBLE HASHING

An extendible hashing scheme resolves bucket overflows by reorganizing the hash function and file structure locally, so it is very suitable for fast key retrievals of dynamic key sets. However, it cannot search keys that contain a given string as substrings efficiently. In this p aper, in order to design this substring search in extendible hashing, sig nature vectors are introduced as hash values, and a trie structure as an extendible hash table, where each vector is composed by a bit s tream. Pseudo signature vectors are defined to identify the buckets, a nd a constrained depth-fir st search is presented to traverse the arcs of the trie structure. To construct a compact trie despite an increas e in the number of keys, uniform signature treetops are introduced, an d the method for an incremental expansion of the hash table is propose d. This approach can restrict the size of the bit stream for each key, making constrained depth-first search efficient. From simulation resu lts, by applying the presented schemes to Japanese and English key set s, it was shown that the number of accessed buckets decreased from 40% to 10% in comparison with traditional extendible hashing for which on ly descriptors were used. In addition, the search time cost of the pre sented approach is 2-10 times faster. (C) 1998 Elsevier Science Inc. A ll rights reserved.