BlockB-Tree: A new index structure combined compact B+-tree with block distance

To overcome the "curse of dimensionality", the high-efficient index structures which map the high-dimensional data to single dimension values are proposed. None of these index structures can support the use of block distance for similarity search directly. Block distance is one of the widely used similarity measurement algorithms in CBIR, and it is very simple and has excellent query performance. In this paper, these two algorithms are effectively combined, and the BlockB-Tree is proposed. The BlockB-Tree uses the block distance to map the high-dimensional feature data to single dimension key values, and then uses the compact B+-tree to manage these key values. It can not only directly support the use of block distance for similarity search, but also can effectively support the use of Euclidean distance for similarity search.