A New Cell-Level Search Based Non-Exhaustive Approximate Nearest Neighbor (ANN) Search Algorithm in the Framework of Product Quantization
| Autor: | Rui Li, Yang Wang, Zhibin Pan |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
0209 industrial biotechnology
Speedup General Computer Science Computer science General Engineering 02 engineering and technology Cellular level k-nearest neighbors algorithm 020901 industrial engineering & automation vector-level search product quantization Search algorithm 0202 electrical engineering electronic engineering information engineering partial distance search 020201 artificial intelligence & image processing General Materials Science Product quantization lcsh:Electrical engineering. Electronics. Nuclear engineering cell-level search Approximate nearest neighbor search lcsh:TK1-9971 Algorithm Computer Science::Databases |
| Zdroj: | IEEE Access, Vol 7, Pp 37059-37070 (2019) |
| ISSN: | 2169-3536 |
| DOI: | 10.1109/access.2019.2900730 |
| Popis: | Non-exhaustive search is widely used in the approximate nearest neighbor (ANN) search. In this paper, we propose a new cell-level search-based non-exhaustive ANN search algorithm in the framework of product quantization (PQ) called cell-level PQ to speed up the ANN search. The cell-level search is introduced by searching all the PQ cells of the query vector on the cell level, and the length of the candidate list can be significantly reduced with negligible computational costs. Instead of using the high time-consuming coarse quantizers, which are necessary in all of the existing non-exhaustive ANN search algorithms such as inverted files (IVFs) and inverted multi-index (IMI), our proposed cell-level PQ reuses the PQ cells of query vector to reject database vectors so that the ANN search in the framework of PQ can be efficiently speeded up. In addition, because our proposed cell-level PQ does not need to store the auxiliary indexes of coarse quantizers for each database vector, no extra memory consumption is required. The experimental results on different databases demonstrate that our proposed cell-level PQ can significantly speed up the ANN search in the framework of PQ, and meanwhile, the search accuracy is almost the same as that of the standard PQ. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|