An efficient algorithm for approximated self-similarity joins in metric spaces

作者：

Highlights：

• The proposed algorithm computes a subquadratic number of distances in the worst case.

• An average precision of 52% of correct nearest neighbors is reached.

• The algorithm offers a viable alternative for k-NN self-similarity joins compared with others.

摘要

•The proposed algorithm computes a subquadratic number of distances in the worst case.•An average precision of 52% of correct nearest neighbors is reached.•The algorithm offers a viable alternative for k-NN self-similarity joins compared with others.

论文关键词：Similarity joins,kNN,Approximated nearest neighbors,Algorithms,Metric spaces

论文评审过程：Received 11 September 2019, Revised 28 January 2020, Accepted 19 February 2020, Available online 24 February 2020, Version of Record 4 March 2020.

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