Joohyoun Park and J. Nang (Korea)
Multimedia Retrieval, similarity search, high dimensional indexing.
Recently, some researches for NN (nearest neighbour) search in multimedia retrieval, for example, the VA-file [11] and the LPC-file [12], have been proposed to resolve the problem called “curse of dimensionality”[17]. They are called as filtering approach because they first filter out the irrelevant objects by scanning all object approximations and compute the distances between the query and remaining objects to find out exact NN. In this approach, since all approximations are scanned in the filtering step, the efficiency of computation in the filtering process must be seriously considered. Otherwise, it would be very hard to be used in the real applications with a lot of multimedia objects. This paper proposes an efficient indexing mechanism for NN search to speed-up this filtering process using a novel indexing structure, called hierarchical bitmap, in which each object is represented as a bitmap of size 2·d where d is the dimension of object’s feature vector. That is, i-th feature value ( di ≤≤1 ) of object is approximated with two bits that represent whether it is relatively high, low, or neither compared to the i-th feature value of other objects. As performing XOR operation between two bitmaps, we can calculate the lower bound of L -distance between two feature vectors. This mechanism can be hierarchically applied to generate multiple bitmaps of a vector in order to raise the filtering rate. p
Important Links:
Go Back
