The LSDh-tree:: An access structure for feature vectors

Efficient access structures far similarity queries on feature vectors are an important research topic for application areas such as multimedia databases, molecular biology or time series analysis. Recently different access structures for high dimensional feature vectors have been proposed - namely the SS-tree, the VAMSplit R-tree, the TV-tree, the SS-tree and the X-tree. All these access structures are derived from the R-tree. As a consequence, the fanout of the directory of these access structures decreases drastically for higher dimensions. Therefore we argue that the R-tree a's not the best possible starting point for the derivation of an access structure for high-dimensional data. We show that k-d-tree-based access structures are at least as well suited for this application area and we introduce the LSDh-tree as an example for such a k-d-tree-based access structure for high-dimensional feature vectors. We describe the algorithms for the LSDh-tree and present experimental results comparing the LSDh-tree and the X-tree.