BLBTree: an Efficient Index Structure for Fast Search

Abstract

Due of its interest in different areas, similarity search in high-dimensional spaces is one of the principal research axes today for CBIR Systems. The properties for high-dimensional data demand some adequate search methods to have a research in optimal time. Due to the curse of dimensionality, search time in the index structure exponentially increases, according the dimension of the descriptor. However, the performances of classical index structures become less than the sequential scan of data in search time when answering exact nearest neighbor queries. To overcome this problematic, two major approaches for high-dimensional data in CBIR systems have been proposed: The first approach permits to speed up the search by using multiple levels of lower bound distances, the second approach exploits the BTree index structure to speed up the search. We propose to combine both techniques to search for large nearest neighbors in a high-dimensional space. We develop a new multidimensional index structure, called BLBTree. In BLBTree, instead of computing the distances in the high-dimensional original space to find the nearest neighbor, lot of candidates are to be rejected based on the lower bound distances: the research in BLBTree does not calculate the distances in the high-dimensional original space to find the nearest neighbor if the lower bounding distance exceeds the threshold, because the distances in the high-dimensional cannot be lower than the distances in the low-dimensional. We note that each object in BLBTree is described by a pyramid structure of histograms, with each histogram representing the lower resolution of the other histogram; due to this property, our index structure is well-suited for high-dimensional and large-scale problems. We have shown that our approach provides interesting and powerful experimental results.
Copyright © 2016 Praise Worthy Prize - All rights reserved.