Probabilistic analysis of vantage point trees
Open Access
- 4 August 2021
- journal article
- research article
- Published by VTeX in Modern Stochastics: Theory and Applications
- Vol. 8 (4), 413-434
- https://doi.org/10.15559/21-vmsta188
Abstract
Publisher: VTeX - Solutions for Science Publishing, Journal: Modern Stochastics - Theory and Applications, Title: Probabilistic analysis of vantage point trees, Authors: Vladyslav Bohun , 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.
Keywords
This publication has 10 references indexed in Scilit:
- On the diminishing process of Bálint TóthTransactions of the American Mathematical Society, 2016
- The diminishing segment processStatistics & Probability Letters, 2012
- ProbabilityPublished by Cambridge University Press (CUP) ,2010
- Dynamic vp-tree indexing for n-nearest neighbor search given pair-wise distancesThe VLDB Journal, 2000
- Convergence of Probability MeasuresWiley Series in Probability and Statistics, 1999
- Adjoint Transform, Overconvexity and Sets of Constant WidthTransactions of the American Mathematical Society, 1992
- The uniform convergence of nearest neighbor regression function estimators and their application in optimizationIEEE Transactions on Information Theory, 1978
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975
- Estimation by the nearest neighbor ruleIEEE Transactions on Information Theory, 1968
- Nearest neighbor pattern classificationIEEE Transactions on Information Theory, 1967