Parallel High-Dimensional Index Structure Using Cell-Based Filtering for Multimedia Data

摘要

A large number of high-dimensional index structures suffer from the so called 'dimensional curse' problem, i.e., the retrieval performance becomes increasingly degraded as the dimensionality is increased. To solve this problem, the cell-based filtering scheme has been proposed, but it shows a linear decrease in performance as the dimensionality is increased. In this paper, we propose a parallel high-dimensional index structure using the cell-based filtering for multimedia data so as to cope with the linear decrease in retrieval performance. In addition, we devise data insertion, range query and κ-NN query processing algorithms which are suitable for the cluster-based parallel architecture. Finally, we show that our parallel index structure achieves good retrieval performance in proportion to the number of servers in the cluster-based architecture and it outperforms a parallel version of the VA-File when the dimensionality is over 10.