Effective optimizations of cluster-based nearest neighbor search in high-dimensional space
详细信息 查看全文
- 作者：Xiaokang Feng ; Jiangtao Cui ; Yingfan Liu ; Hui Li
- 关键词：Image retrieval ; Nearest neighbor search ; High ; dimensional indexing ; Hyperplane bounds
- 刊名：Multimedia Systems
- 出版年：2017
- 出版时间：February 2017
- 年：2017
- 卷：23
- 期：1
- 页码：139-153
- 全文大小：
- 刊物类别：Computer Science
- 刊物主题：Multimedia Information Systems; Computer Communication Networks; Operating Systems; Data Storage Representation; Data Encryption; Computer Graphics;
- 出版者：Springer Berlin Heidelberg
- ISSN：1432-1882
- 卷排序：23
文摘
Nearest neighbor (NN) search in high-dimensional space plays a fundamental role in large-scale image retrieval. It seeks efficient indexing and search techniques, both of which are simultaneously essential for similarity search and semantic analysis. However, in recent years, there has been a rare breakthrough. Achievement of current techniques for NN search is far from satisfactory, especially for exact NN search. A recently proposed method, HB, addresses the exact NN search efficiently in high-dimensional space. It benefits from cluster-based techniques which can generate more compact representation of the data set than other techniques by exploiting interdimensional correlations. However, HB suffers from huge cost for lower bound computations and provides no further pruning scheme for points in candidate clusters. In this paper, we extend the HB method to address exact NN search in correlated, high-dimensional vector data sets extracted from large-scale image database by introducing two new pruning/selection techniques and we call it HB+. The first approach aims at selecting more quickly the subset of hyperplanes/clusters that must be considered. The second technique prunes irrelevant points in the selected subset of clusters. Performed experiments show the improvement of HB+ with respect to HB in terms of efficiency (I/O cost and CPU response time) and also demonstrate the superiority over other exact NN indexes.