Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Flexible product quantization for fast approximate nearest neighbor search

  • Published:
Multimedia Tools and Applications Aims and scope Submit manuscript

Abstract

Product quantization (PQ) is an effective solution to approximate nearest neighbor (ANN) search. The idea of PQ is to decompose the space into Cartesian product of several low-dimensional subspaces and quantize each subspace separately. Database vectors are represented by short codes with different length composed of their subspace quantization indices. A vector is encoded to a short code consisting of its subspace quantization indices. PQ allows to generate a large size codebook with very low memory and time cost, and the selection of the number M of sub-vectors is the most essential and important problem, but is easily neglected. Motivated by this observation, we propose a method named Flexible Product quantization (FPQ) to optimize PQ-based methods that fix M for all vectors. FPQ achieves flexible M by concatenating the sub-vector pairs through constrains on quantization distortion. The concatenating operation is implemented individually among different database vectors and can lead to far less additions in the search process. Different from existing PQ-based fast search methods, this operation of our proposed FPQ is to reduce the computational complexity for searching each single database vector, which provides a new perspective to better accelerate ANN search. Experimental results show that our method for product quantization based methods can significantly reduce nearly 25\(\%\) computational complexity by using appropriate parameters, while the search accuracy can be guaranteed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Algorithm 2
Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Data Availibility Statement

The datasets that support the findings of this study are openly available at http://corpus-texmex.irisa.fr. The program that supports the findings of this study is available from the corresponding author,upon request.

References

  1. Boiman O, Shechtman E, Irani M (2008) In defense of nearest-neighbor based image classification. In: 2008 IEEE Conference on computer vision and pattern recognition, pp 1–8

  2. Wang J, Wen C (2011) Personalized commodity recommending method and system which integrate attributes and structural similarity

  3. Zhang S, Li X, Zong M, Zhu X, Wang R (2017) Efficient knn classification with different numbers of nearest neighbors. IEEE Trans Neural Netw Learn Syst 29(5):1774–1785

    Article  MathSciNet  Google Scholar 

  4. Pan Y, Pan Z, Wang Y, Wang W (2020) A new fast search algorithm for exact k-nearest neighbors based on optimal triangle-inequality-based check strategy. Knowl-Based Syst 189

  5. Indyk P, Motwani R (1998) Approximate nearest neighbors: towards removing the curse of dimensionality. In: Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp 604–613

  6. Liu W, Wang J, Ji R, Jiang Y-G, Chang S-F (2012) Supervised hashing with kernels. In: 2012 IEEE Conference on computer vision and pattern recognition, pp 2074–2081

  7. Ercoli S, Bertini M, Bimbo AD (2017) Compact hash codes for efficient visual descriptors retrieval in large scale databases. IEEE Trans Multimed 19(11):2521–2532

    Article  Google Scholar 

  8. Wang J, Kumar S, Chang S-F (2012) Semi-supervised hashing for large-scale search. IEEE Trans Patt Anal Mach Intell 34(12):2393–2406

    Article  Google Scholar 

  9. Jin L, Li Z, Tang J (2020) Deep semantic multimodal hashing network for scalable image-text and video-text retrievals. IEEE Trans Neural Netw Learn Syst 34(4):1838–1851

    Article  Google Scholar 

  10. Li Z, Tang J, Zhang L, Yang J (2020) Weakly-supervised semantic guided hashing for social image retrieval. Int J Comp Vision 128:2265–2278

    Article  MathSciNet  Google Scholar 

  11. Jégou H, Douze M, Schmid C (2011) Product quantization for nearest neighbor search. IEEE Trans Patt Anal Mach Intell 33(1):117–128

    Article  Google Scholar 

  12. Song W, Wang Y, Pan Z (2023) A novel cell partition method by introducing Silhouette Coefficient for fast approximate nearest neighbor search. Inf Sci 642:119216

  13. Pan Z, Wang L, Wang Y, Liu Y (2020) Product quantization with dual codebooks for approximate nearest neighbor search. Neurocomputing 401:59–68

    Article  Google Scholar 

  14. Fan F, Pan Z,Wang L,WangY (2022) Codebook-softened product quantization for high accuracy approximate nearest neighbor search. Neurocomputing 507(1):107–116

  15. Ge T, He K, Ke Q, Sun J (2014) Optimized product quantization. IEEE Trans Patt Anal Mach Intell 36(4):744–755

    Article  Google Scholar 

  16. Kalantidis Y, Avrithis Y (2014) Locally optimized product quantization for approximate nearest neighbor search. In: 2014 IEEE Conference on computer vision and pattern recognition, pp 2329–2336

  17. Norouzi M, Fleet DJ (2013) Cartesian k-means. In: 2013 IEEE Conference on computer vision and pattern recognition, pp 3017–3024

  18. Hong W, Tang X, Meng J, Yuan J (2020) Asymmetric mapping quantization for nearest neighbor search. IEEE Trans Patt Anal Mach Intell 42(7):1783–1790

    Article  Google Scholar 

  19. Heo J-P, Lin Z, Yoon S-E (2019) Distance encoded product quantization for approximate k-nearest neighbor search in high-dimensional space. IEEE Trans Patt Anal Mach Intell 41(9):2084–2097

    Article  Google Scholar 

  20. Li L, Hu Q, Han Y, Li X (2018) Distribution sensitive product quantization. IEEE Trans Circ Syst Video Tech 28(12):3504–3515

    Article  Google Scholar 

  21. Ning Q, Zhu J, Zhong Z, Hoi SC, Chen C (2017) Scalable image retrieval by sparse product quantization. IEEE Trans Multimed 19(3):586–597

    Article  Google Scholar 

  22. An S, Huang Z, Bai S, Che G, Ma X, Luo J, Chen Y (2019) Quarter-point product quantization for approximate nearest neighbor search. Pattern Recogn Lett 125:187–194

    Article  Google Scholar 

Download references

Acknowledgements

This work is supported in part by the National Natural Science Foundation of China (Grant No. U1903213), The Ph.D. Stand-up Fund of Xi’an University of Technology (Grant No. 108-451121002) and the Zhejiang Provincial Commonweal Project (Grant No. LGF21F030002).

Author information

Authors and Affiliations

  1. Faculty of Electronic and Information Engineering, Xi’an Jiaotong University, Xi’an, Shaanxi, 710049, People’s Republic of China

    Jingya Fan, Wenwen Song & Zhibin Pan

  2. Department of Information Science, Xi’an University of Technology, Xi’an, Shaanxi, 710048, People’s Republic of China

    Yang Wang

  3. Research Institute of Xi’an Jiaotong University, Zhejiang, 311215, People’s Republic of China

    Zhibin Pan

Authors
  1. Jingya Fan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yang Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Wenwen Song
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Zhibin Pan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zhibin Pan.

Ethics declarations

Conflicts of interest

We declare that we have no financial and personal relationships with other people or organizations that can inappropriately influence our work, and there is no professional or other personal interest of any nature or kind in any product, service and/or company that could be construed as influencing the position presented in the manuscript entitled “Flexible Product Quantization for Fast Approximate Nearest Neighbor Search”.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Fan, J., Wang, Y., Song, W. et al. Flexible product quantization for fast approximate nearest neighbor search. Multimed Tools Appl 83, 53243–53261 (2024). https://doi.org/10.1007/s11042-023-17564-3

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11042-023-17564-3

Keywords

Search

Navigation