1. Home
  2. Issues
  3. Volume 8, Issue 4 (2021)
  4. Probabilistic analysis of vantage point ...

Modern Stochastics: Theory and Applications


Probabilistic analysis of vantage point trees
Volume 8, Issue 4 (2021), pp. 413–434
Pub. online: 4 August 2021      Type: Research Article      Open accessOpen Access
Received
27 April 2021
Revised
8 July 2021
Accepted
8 July 2021
Published
4 August 2021

Abstract

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.

References

[1] 
Ambrus, G., Kevei, P., Vigh, V.: The diminishing segment process. Stat. Probab. Lett. 82(1), 191–195 (2012). MR2863042. https://doi.org/10.1016/j.spl.2011.09.016
[2] 
Bavaud, F.: Adjoint transform, overconvexity and sets of constant width. Trans. Am. Math. Soc. 333(1), 315–324 (1992). MR1132431. https://doi.org/10.2307/2154111
[3] 
Bentley, J.: Multidimensional binary search trees used for associative searching. Commun. ACM 18(9), 509–517 (1975)
[4] 
Billingsley, P.: Convergence of Probability Measures, Second Edition. John Wiley & Sons, Inc., New York (1999). MR1700749. https://doi.org/10.1002/9780470316962
[5] 
Cover, T.: Estimation by the nearest neighbor rule. IEEE Trans. Inf. Theory 14(1), 50–55 (1968)
[6] 
Cover, T., Hart, P.: Nearest neighbor pattern classification. IEEE Trans. Inf. Theory 13(1), 21–27 (1967)
[7] 
Devroye, L.: The uniform convergence of nearest neighbor regression function estimators and their applications in optimization. IEEE Trans. Inf. Theory 24(2), 142–151 (1978). MR0518942. https://doi.org/10.1109/tit.1978.1055865
[8] 
Durrett, R.: Probability Theory and Examples, Fourth Edition. Cambridge University Press, New York (2010). MR2722836. https://doi.org/10.1017/CBO9780511779398
[9] 
Fu, A., Chan, P., Cheung, Y., Moon, Y.: Dynamic vp-tree indexing for n-nearest neighbor search given pair-wise distances. VLDB J. 9, 154–173 (2000)
[10] 
Kevei, P., Vigh, V.: On the diminishing process of Balint Toth. Trans. Am. Math. Soc. 368(12), 8823–8848 (2016). MR3551590. https://doi.org/10.1090/tran/6620
[11] 
Kumar, N., Zhang, L., Nayar, S.: What is a good nearest neighbors algorithm for finding similar patches in images. In: Lecture Notes in Computer Science, Vol 5303, pp. 364–378. Springer, Berlin (2008)
[12] 
Moore, A.: An introductory tutorial on kd-trees. Technical Report Technical Report No. 209, Computer Laboratory, University of Cambridge, Carnegie Mellon University, Pittsburgh, PA (1991)
[13] 
Narasimhulu, Y., Suthar, A., Pasunuri, R., Venkaiah, V.: Ckd-tree: An improved kd-tree construction algorithm. In: International Semantic Intelligence Conference 2021, pp. 211–218 (2021)
[14] 
Omohundro, S.: Five balltree construction algorithms. Technical Report Technical Report 89-063 (1989)
[15] 
Papernot, N., McDaniel, P.: Deep k-nearest neighbors: Towards confident, interpretable and robust deep learning. CoRR 1803.04765 (2018)
[16] 
Shishibori, M., Lee, S., Kita, K.: An improved method to select candidates on metric index vp-tree. In: Proceedings of the International Conference on Knowledge Discovery and Information Retrieval, vol. 1, pp. 306–311 (2011)
[17] 
Yianilos, P.: Data structures and algorithms for nearest neighbor search in general metric spaces. In: Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 311–321 (1993). MR1213243

Full article Related articles PDF XML
Full article Related articles PDF XML

Copyright
© 2021 The Author(s). Published by VTeX
Open access article under the CC BY license.

Keywords
Fixed-point equation machine learning Markov chain nearest neighbor search probabilistic analysis random tree similarity search vantage point tree vp-tree

MSC2010
60F05 60J05 60J20 68P05 68W40

Funding
The author was supported by the National Research Foundation of Ukraine (project 2020.02/0014 “Asymptotic regimes of perturbed random walks: on the edge of modern and classical probability”).

Metrics (since March 2018)
2546

Article info
views

 1486

Full article
views
1176

PDF
downloads

 1007

XML
downloads


Share


RSS