Compressed cover tree
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
The compressed cover tree is a type of data structure in computer science that is specifically designed to facilitate the speed-up of a k-nearest neighbors algorithm in finite metric spaces. Compressed cover tree is a simplified version of explicit representation of cover tree that was motivated by past issues in proofs of time complexity results of cover tree. The compressed cover tree was specifically designed to achieve claimed time complexities of cover tree in a mathematically rigorous way.
Evidence and sources
The compressed cover tree is a type of data structure in computer science that is specifically designed to facilitate the speed-up of a k-nearest neighbors algorithm in finite metric spaces. Compressed cover tree is a simplified version of explicit representation of cover tree that was motivated by past issues in proofs of time complexity results of cover tree. The compressed cover tree was specifically designed to achieve claimed time complexities of cover tree in a mathematically rigorous way.
Separation condition: For i \in \Z , the cover set C_i = \{p \in R \mid l(p) \geq i\} has d_{\min}(C_i) = \min\limits_{p \in C_{i}}\min\limits_{q \in C_{i}\setminus \{p\}} d(p,q) > 2^{i} the new minimized expansion constant c_m is a discrete analog of the doubling dimension Navigating nets c_m(R) = \lim\limits_{\xi \rightarrow 0^{+}}\inf\limits_{R\subseteq A\subseteq X}\sup\limits_{p \in A,t > \xi}\dfrac , where A is a locally finite set which covers R. Note that c_m(R) \leq c(R) for any finite metric space (R,d).
For any finite set R with a metric d, the diameter is \mathrm{diam}(R) = \max_{p \in R}\max_{q \in R}d(p,q) . The aspect ratio is \Delta(R) = \dfrac{\mathrm{diam}(R)}{d_{\min}(R)} , where d_{\min}(R) is the shortest distance between points of R.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1317539473 under CC BY-SA 4.0; modifications have been made.