Perfect Hash Table Algorithm for Image Databases using Negative Associated Values

Abstract

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. © 1995.

Department(s)

Computer Science

Keywords and Phrases

2D string; Associated value function; Image database systems; Perfect hashing; Spatial reasoning; Storage and retrieval

International Standard Serial Number (ISSN)

0031-3203

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2024 Elsevier, All rights reserved.

Publication Date

01 Jan 1995

Link to Full Text

Share

 
COinS