Details

Autor(en) / Beteiligte

• Houle, Michael E.
• Nett, Michael

Titel

Rank Cover Trees for Nearest Neighbor Search

Ist Teil von

• Similarity Search and Applications, p.16-29

Ort / Verlag

Berlin, Heidelberg: Springer Berlin Heidelberg

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• This paper introduces a k-NN search index, the Rank Cover Tree (RCT), whose pruning tests rely solely on the comparison of similarity values; other properties of the underlying space, such as the triangle inequality, are not employed. A formal theoretical analysis shows that with very high probability, the RCT returns a correct query result in time that depends competitively on a measure of the intrinsic dimensionality of the data set. Experiments show that the RCT is capable of meeting or exceeding the level of performance of state-of-the-art methods that make use of metric pruning or selection tests involving numerical constraints on distance values.