| 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] |
¡@
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.
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.