HVA-Index: An efficient indexing method for similarity search in high-dimensional vector spaces

摘要

High-dimensional indexing plays a critical role in multidimensional data retrieval. In this work, we propose a new indexing method, named HVA-Index, for similarity search in high-dimensional vector space. This index is based on Vector Approximation and Hash Table. The outstanding advantage is that it stores all vectors in a hash table using approximation as key, and the vectors fall into same cell are organized in a linked list. Contrast to VA-File, the HVA-Index doesn't require scan the entire approximation file, and efficiently improves the speed of similarity search. Our experiments prove that HVA-Index outperforms both of the VA-File and the sequential scan in total elapsed time and the number of disk access, and it's still effective at high dimensionality.