Online Additive Quantization

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

doi:10.1145/3447548.3467441

Online Additive Quantization

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 Scopus citations

Abstract

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 language	English (US)
Title of host publication	KDD 2021 - Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
Publisher	Association for Computing Machinery
Pages	1098-1108
Number of pages	11
ISBN (Electronic)	9781450383325
DOIs	https://doi.org/10.1145/3447548.3467441
State	Published - Aug 14 2021
Externally published	Yes
Event	27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2021 - Virtual, Online, Singapore Duration: Aug 14 2021 → Aug 18 2021

Publication series

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

Conference

Conference	27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2021
Country/Territory	Singapore
City	Virtual, Online
Period	8/14/21 → 8/18/21

Keywords

additive quantization
beam search
nearest neighbor search
online update

ASJC Scopus subject areas

Software
Information Systems

Access to Document

10.1145/3447548.3467441

Cite this

Liu, Q., Zhang, J., Lian, D., Ge, Y., Ma, J., & Chen, E. (2021). Online Additive Quantization. In KDD 2021 - Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 1098-1108). (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining). Association for Computing Machinery. https://doi.org/10.1145/3447548.3467441

Online Additive Quantization. / Liu, Qi; Zhang, Jin; Lian, Defu et al.
KDD 2021 - Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery, 2021. p. 1098-1108 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Liu, Q, Zhang, J, Lian, D, Ge, Y, Ma, J & Chen, E 2021, Online Additive Quantization. in KDD 2021 - Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Association for Computing Machinery, pp. 1098-1108, 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2021, Virtual, Online, Singapore, 8/14/21. https://doi.org/10.1145/3447548.3467441

@inproceedings{7107d0e854d04f8ba345ac94fd853f20,

title = "Online Additive Quantization",

abstract = "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.",

keywords = "additive quantization, beam search, nearest neighbor search, online update",

author = "Qi Liu and Jin Zhang and Defu Lian and Yong Ge and Jianhui Ma and Enhong Chen",

note = "Publisher Copyright: {\textcopyright} 2021 ACM.; 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2021 ; Conference date: 14-08-2021 Through 18-08-2021",

year = "2021",

month = aug,

day = "14",

doi = "10.1145/3447548.3467441",

language = "English (US)",

series = "Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

publisher = "Association for Computing Machinery",

pages = "1098--1108",

booktitle = "KDD 2021 - Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining",

}

TY - GEN

T1 - Online Additive Quantization

AU - Liu, Qi

AU - Zhang, Jin

AU - Lian, Defu

AU - Ge, Yong

AU - Ma, Jianhui

AU - Chen, Enhong

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 - https://www.scopus.com/pages/publications/85114909477

UR - https://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 -

Online Additive Quantization

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this