Image Databases and Near-Perfect Hash Table
Abstract
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. © 1997 Pattern Recognition Society. Published by Elsevier Science Ltd.
Recommended Citation
C. Sabharwal and S. K. Bhatia, "Image Databases and Near-Perfect Hash Table," Pattern Recognition, vol. 30, no. 11, pp. 1867 - 1876, Elsevier, Jan 1997.
The definitive version is available at https://doi.org/10.1016/S0031-3203(96)00187-2
Department(s)
Computer Science
Keywords and Phrases
Hash addressing; Image database systems; Indexing; Retrieval; Storage
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 1997
