TY - GEN
T1 - Online Additive Quantization
AU - Liu, Qi
AU - Zhang, Jin
AU - Lian, Defu
AU - Ge, Yong
AU - Ma, Jianhui
AU - Chen, Enhong
N1 - Funding Information:
The work was supported by grants from the National Natural Science Foundation of China ?No. 62022077 and 61976198), JD AI Research and the Fundamental Research Funds for the Central Universities ?No. WK2150110017).
Publisher Copyright:
© 2021 ACM.
PY - 2021/8/14
Y1 - 2021/8/14
N2 - 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.
AB - 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.
KW - additive quantization
KW - beam search
KW - nearest neighbor search
KW - online update
UR - http://www.scopus.com/inward/record.url?scp=85114909477&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85114909477&partnerID=8YFLogxK
U2 - 10.1145/3447548.3467441
DO - 10.1145/3447548.3467441
M3 - Conference contribution
AN - SCOPUS:85114909477
T3 - Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
SP - 1098
EP - 1108
BT - KDD 2021 - Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
PB - Association for Computing Machinery
T2 - 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2021
Y2 - 14 August 2021 through 18 August 2021
ER -