Probabilistic analysis of vantage point trees
Probabilistic properties of vantage point trees are studied. A vp-tree built from a sequence of independent identically distributed points in ${[-1,\hspace{0.1667em}1]^{d}}$ with the ${\ell _{\infty }}$-distance function is considered. The length of the leftmost path in the tree, as well as partitio...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
VTeX
2021-08-01
|
| Series: | Modern Stochastics: Theory and Applications |
| Subjects: | |
| Online Access: | https://www.vmsta.org/doi/10.15559/21-VMSTA188 |
| _version_ | 1818822743917854720 |
|---|---|
| author | Vladyslav Bohun |
| author_facet | Vladyslav Bohun |
| author_sort | Vladyslav Bohun |
| collection | DOAJ |
| description | Probabilistic properties of vantage point trees are studied. A vp-tree built from a sequence of independent identically distributed points in ${[-1,\hspace{0.1667em}1]^{d}}$ with the ${\ell _{\infty }}$-distance function is considered. The length of the leftmost path in the tree, as well as partitions over the space it produces are analyzed. The results include several convergence theorems regarding these characteristics, as the number of nodes in the tree tends to infinity. |
| first_indexed | 2024-12-18T23:28:56Z |
| format | Article |
| id | doaj.art-d9dfff7dfd874d459844ae2798bdc000 |
| institution | Directory Open Access Journal |
| issn | 2351-6046 2351-6054 |
| language | English |
| last_indexed | 2024-12-18T23:28:56Z |
| publishDate | 2021-08-01 |
| publisher | VTeX |
| record_format | Article |
| series | Modern Stochastics: Theory and Applications |
| spelling | doaj.art-d9dfff7dfd874d459844ae2798bdc0002022-12-21T20:47:44ZengVTeXModern Stochastics: Theory and Applications2351-60462351-60542021-08-018441343410.15559/21-VMSTA188Probabilistic analysis of vantage point treesVladyslav Bohun0Faculty of Computer Science and Cybernetics, Taras Shevchenko National University of Kyiv, 01601 Kyiv, UkraineProbabilistic properties of vantage point trees are studied. A vp-tree built from a sequence of independent identically distributed points in ${[-1,\hspace{0.1667em}1]^{d}}$ with the ${\ell _{\infty }}$-distance function is considered. The length of the leftmost path in the tree, as well as partitions over the space it produces are analyzed. The results include several convergence theorems regarding these characteristics, as the number of nodes in the tree tends to infinity.https://www.vmsta.org/doi/10.15559/21-VMSTA188Fixed-point equationmachine learningMarkov chainnearest neighbor searchprobabilistic analysisrandom tree |
| spellingShingle | Vladyslav Bohun Probabilistic analysis of vantage point trees Modern Stochastics: Theory and Applications Fixed-point equation machine learning Markov chain nearest neighbor search probabilistic analysis random tree |
| title | Probabilistic analysis of vantage point trees |
| title_full | Probabilistic analysis of vantage point trees |
| title_fullStr | Probabilistic analysis of vantage point trees |
| title_full_unstemmed | Probabilistic analysis of vantage point trees |
| title_short | Probabilistic analysis of vantage point trees |
| title_sort | probabilistic analysis of vantage point trees |
| topic | Fixed-point equation machine learning Markov chain nearest neighbor search probabilistic analysis random tree |
| url | https://www.vmsta.org/doi/10.15559/21-VMSTA188 |
| work_keys_str_mv | AT vladyslavbohun probabilisticanalysisofvantagepointtrees |