English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This paper is motivated by the k-nearest neighbors search: given an arbitrarymetric 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 qin Q. In 2006, Beygelzimer, Kakade, and Langford introduced cover trees tojustify a near-linear time complexity for the neighbor search in the sizes ofQ,R.  Section 5.3 of Curtin's PhD (2015) pointed out that the proof of this resultwas wrong. The key step in the original proof attempted to show that the numberof iterations can be estimated by multiplying the length of the longestroot-to-leaf path in a cover tree by a constant factor. However, this estimatecan miss many potential nodes in several branches of a cover tree, that shouldbe considered during the neighbor search. The same argument was unfortunatelyrepeated in several subsequent papers using cover trees from 2006.  This paper explicitly constructs challenging datasets that providecounterexamples to the past proofs of time complexity for the cover treeconstruction, the k-nearest neighbor search presented at ICML 2006, and thedual-tree search algorithm published in NIPS 2009.  The corrected near-linear time complexities with extra parameters are provedin another forthcoming paper by using a new compressed cover tree simplifyingthe original tree structure.

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