Online Additive Quantization

Qi Liu, Jin Zhang, Defu Lian, Yong Ge, Jianhui Ma, Enhong Chen

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Approximate nearest neighbor search (ANNs) plays an important role in many applications ranging from information retrieval, recommender systems to machine translation. Several ANN indexes, such as hashing and quantization, have been designed to update for the evolving database, but there exists a remarkable performance gap between them and retrained indexes on the entire database. To close the gap, we propose an online additive quantization algorithm (online AQ) to dynamically update quantization codebooks with the incoming streaming data. Then we derive the regret bound to theoretically guarantee the performance of the online AQ algorithm. Moreover, to improve the learning efficiency, we develop a randomized block beam search algorithm for assigning each data to the codewords of the codebook. Finally, we extensively evaluate the proposed online AQ algorithm on four real-world datasets, showing that it remarkably outperforms the state-of-the-art baselines.

Original languageEnglish (US)
Title of host publicationKDD 2021 - Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
PublisherAssociation for Computing Machinery
Number of pages11
ISBN (Electronic)9781450383325
StatePublished - Aug 14 2021
Externally publishedYes
Event27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2021 - Virtual, Online, Singapore
Duration: Aug 14 2021Aug 18 2021

Publication series

NameProceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining


Conference27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2021
CityVirtual, Online


  • additive quantization
  • beam search
  • nearest neighbor search
  • online update

ASJC Scopus subject areas

  • Software
  • Information Systems


Dive into the research topics of 'Online Additive Quantization'. Together they form a unique fingerprint.

Cite this