Perfect Hash Table Algorithm for Image Databases Using Negative Associated Values

A 2D string data structure allows for efficient spatial reasoning on an image database for query and retrieval. A 2D string can be converted to a set of triples leading to an elegant  O (1) solution for image retrieval with simple queries using a perfect hash table. For complex queries, the retrieval complexity is linear in this approach and depends on the number of possible pairings of picture objects in the query. The perfect hash table computation for this problem is mapped directly to a permutation problem. In an earlier paper [S. K. Bhatia and C. L. Sabharwal,  Pattern Recognition 27, 365–376 (1974)], we presented a set of heuristics that result in a fast computation of associated values, for picture objects, used in the calculation of hash addresses. In this paper, we present an additional heuristic leading to a 90% reduction in search space over our earlier algorithm. The new heuristic promises to generate a minimal perfect hash function for each experimental data set, which was not possible with the earlier algorithms. Mathematical analysis of complexity of the algorithms is presented and is supported by experimental results.