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

摘要

This paper proposes an efficient indexing mechanism for similarity search in high-dimensional 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.