  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
in 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.
