Counterexamples expose gaps in the proof of time complexity for cover trees introduced in 2006

Elkin, Yury and Kurlin, Vitaliy ORCID: 0000-0001-5328-5351 (2022) Counterexamples expose gaps in the proof of time complexity for cover trees introduced in 2006. In: 2022 Topological Data Analysis and Visualization (TopoInVis), 2022-10-17 - 2022-10-17.

Access the full-text of this item by clicking on the Open Access link.

PDF
cover-tree-counter-examples.pdf - Author Accepted Manuscript
Download (306kB) | Preview

Official URL: http://dx.doi.org/10.1109/topoinvis57755.2022.0000...

Abstract

This paper is motivated by the k-nearest neighbors search: given an arbitrary metric space, and its finite subsets (a reference set R and a query set Q), design a fast algorithm to find all k-nearest neighbors in R for every point q ∈ Q. In 2006, Beygelzimer, Kakade, and Langford introduced cover trees to justify a near-linear time complexity for the neighbor search in the sizes of Q,R.Section 5.3 of Curtin's PhD (2015) pointed out that the proof of this result was wrong. The key step in the original proof attempted to show that the number of iterations can be estimated by multiplying the length of the longest root-to-leaf path in a cover tree by a constant factor. However, this estimate can miss many potential nodes in several branches of a cover tree, that should be considered during the neighbor search. The same argument was unfortunately repeated in several subsequent papers using cover trees from 2006.This paper explicitly constructs challenging datasets that provide counterexamples to the past proofs of time complexity for the cover tree construction, the k-nearest neighbor search presented at ICML 2006, and the dual-tree search algorithm published in NIPS 2009.The corrected near-linear time complexities with extra parameters are proved in another forthcoming paper by using a new compressed cover tree simplifying the original tree structure.

Item Type:	Conference or Workshop Item (Unspecified)
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	28 Mar 2023 09:44
Last Modified:	26 Apr 2024 22:35
DOI:	10.1109/TopoInVis57755.2022.00008
Open Access URL:	https://arxiv.org/abs/2208.09447
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3169282