Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20] [ 21] [ 22] [ 23] [ 24]

@

Journal of Information Science and Engineering, Vol. 26 No. 2, pp. 393-407 (March 2010)

A Hierarchical Bitmap Indexing Method for Similarity Search in High-Dimensional Multimedia Databases*

JONGHO NANG, JOOHYOUN PARK, JIHOON YANG AND SAEJOON KIM
Department of Computer Science and Engineering
Sogang University
Seoul 121-742, Korea

This paper proposes an efficient indexing mechanism for similarity search in highdimensional multimedia database that quickly filter-outs the irrelevant objects using a novel indexing structure, called HBI (Hierarchical Bitmap Index). In this bitmap index, the feature (or attribute) value of object at each dimension is represented with a set of two bits each of which indicates whether it is relatively high ('11'), low ('00'), or neither ('01') compared to the feature values of other objects at a hierarchical organized interval. This approximation helps to reduce the CPU time of filtering process because many irrelevant objects could be simply excluded by just XORing the bitmaps of two objects. Upon experimental results, we find that there is an optimal number of bitmaps that keeps the filtering rate as high as possible while keeping the search time as short as possible. Furthermore, we also find that the similarity search using the proposed indexing mechanism is about 2-3 times faster than VA-File while guaranteeing the exact solutions.

Keywords: multimedia retrieval, similarity search, high dimensional indexing, hierarchical bitmap indexing, curse of dimensionality

Full Text () Retrieve PDF document (201003_05.pdf)

Received June 19, 2008; revised September 18, 2008; accepted March 19, 2009.
Communicated by Suh-Ying Lee.
* This is an extended version of paper, titled An Efficient Indexing Structure for Content Based Multimedia Retrieval with Relevance Feedback in Proceedings of ACM Symposium on Applied Computing, Vol. 1, 2007, pp. 517-524.