Similarity Query Processing for High-dimensional Data

CategoryPublications Publications 227

Authors: Jianbin Qin, Wei Wang, Chuan Xiao, Ying Zhang

Name of Conference: International Conference on Very Large Data Bases (VLDB 2020), Aug 31- Sept 4, 2020, Tokyo, Japan

Date of Publication: Aug 31, 2020


Similarity query processing has been an active research topic for several decades. It is an essential procedure in a wide range of applications. Recently, embedding and auto-encoding methods as well as pre-trained models have gained popularity. They basically deal with high-dimensional data, and this trend brings new opportunities and challenges to similarity query processing for high-dimensional data. Meanwhile, new techniques have emerged to tackle this long-standing problem theoretically and empirically. In this tutorial, we summarize existing solutions, especially recent advancements from both database (DB) and machine learning (ML) communities, and analyze their strengths and weaknesses. We review exact and approximate methods such as cover tree, locality sensitive hashing, product quantization, and proximity graphs. We also discuss the selectivity estimation problem and show how researchers are bringing in state-of-the-art ML techniques to address the problem. By highlighting the strong connections between DB and ML, we hope that this tutorial provides an impetus towards new ML for DB solutions and vice versa.

View Full Text

Keywords2020Data qualityJianbin QinVLDB Previous: Next: