A Model of the Distribution of Distances between Random Points in High-Dimensional Spaces

Résumé fourni par la source

Abstract A model of the approximate distribution of distances between random points in a high-dimensional space (when the dimension tends to infinity) is constructed. Statistical properties of distances between random points in an n-dimensional hypercube are analyzed. An exact distance distribution function is constructed between random uniformly distributed points in the range of values depending on the dimension of the hypercube. Also, an exact asymptotic distribution of distances between random points with increasing dimension is constructed for the case when the coordinates of the points are independent identically distributed random variables. This problem is very important in the context of approximate search for nearest neighbors among a set of multidimensional vectors. The exact asymptotic distribution of distances in a hypercube makes it possible to correctly approximate the distribution of distances between random points in a space of a high but finite dimension. On this basis, a model of a priori accuracy estimation is proposed to find the nearest neighbor to a multidimensional vector belonging to a certain set of vectors in a hypercube.

Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.