Signature-Based Hybrid Spill-Tree for Indexing High-Dimensional Data

Because video data, especially UCC (User Create Content), has recently attracted much interest, high-dimensional indexing schemes are required to support the content-based retrieval of video data. However, most high-dimensional indexing schemes, except Hybrid Spill-Tree, are not efficient in terms of retrieval performance because they are weak in either retrieval accuracy or retrieval time. Therefore, we, in this paper, propose a new efficient high-dimensional indexing scheme to support the content-based retrieval of a large amount of video data. For this, we extend Hybrid Spill-tree by using a newly designed clustering technique and by adopting a signature technique. In addition, we provide both an insertion algorithm and a k-NN search algorithm for our high-dimensional indexing scheme. Finally, we show that our signature-based high-dimensional indexing scheme achieves better retrieval performance than M-Tree and Hybrid Spill-Tree.