Image databases and near-perfect hash table

The 2D-string is one of the important data structures to represent spatial information in images and has been used to perform queries in image database systems. A 2D string can be readily converted to a set of triples which can be used to generate a perfect hash table for indexing the image database. The perfect hash table allows for O(1) retrieval in image database but the computation of the hash table itself, by the fastest heuristic algorithm, is of exponential time complexity. Every time the database is modified, the hash table needs to be recomputed. This limits the use of the hash table to applications where the image database is relatively fixed, such as the ones found on a CD-ROM. In this paper, we present an enhancement of the perfect hash table to allow for insertion and deletion in the hash table. The new hash table allows for a relatively small number of collisions and is called near-perfect hash table. It provides the flexibility of a live database while closely approximating the efficiency of retrieval with the perfect hash table as shown by the asymptotic analysis of the search procedure. (C) 1997 Pattern Recognition Society. Published by Elsevier Science Ltd.