Query filtering using two-dimensional local embeddings

作者：

Highlights：

• The four-point property possessed by many metric spaces is used to create very small object proxies

• Distances between these proxies are a lower bound of the true distance

• Fast approximate kNN query with high precision and recall can be achieved

• The mechanism can be added to other search techniques with negligible extra cost

• The mechanisms described are well suited to a GPU implementation

摘要

•The four-point property possessed by many metric spaces is used to create very small object proxies•Distances between these proxies are a lower bound of the true distance•Fast approximate kNN query with high precision and recall can be achieved•The mechanism can be added to other search techniques with negligible extra cost•The mechanisms described are well suited to a GPU implementation

论文关键词：Metric search,Extreme pivoting,Supermetric space,Four-point property,Pivot based index

论文评审过程：Received 14 March 2020, Revised 4 January 2021, Accepted 17 May 2021, Available online 21 May 2021, Version of Record 18 June 2021.

论文官网地址：https://doi.org/10.1016/j.is.2021.101808