A survey on graph-based methods for similarity searches in metric spaces
作者：
Highlights：
• Review of graph-based methods for similarity searches categorized by graph type.
• Discussion on the applicability and exactness of search algorithms in each graph type.
• Tradeoff between graph construction and search performance according to parameters.
• For a given recall rate, no graph type was the winner for all cases.
• Dimensionality and graph connectivity affects the graph performance.
摘要
•Review of graph-based methods for similarity searches categorized by graph type.•Discussion on the applicability and exactness of search algorithms in each graph type.•Tradeoff between graph construction and search performance according to parameters.•For a given recall rate, no graph type was the winner for all cases.•Dimensionality and graph connectivity affects the graph performance.
论文关键词：Graph-based methods,Proximity graphs,Similarity searches,Metric spaces,Experimental survey
论文评审过程：Received 13 August 2019, Revised 1 December 2019, Accepted 27 January 2020, Available online 25 February 2020, Version of Record 15 October 2020.
论文官网地址：https://doi.org/10.1016/j.is.2020.101507
