On the Nearest Neighbor of the Nearest Neighbor in Multidimensional Continuous and Quantized Space
Riccardo Rovatti, G. Mazzini · IEEE Transactions on Information Theory · 2008
The probability that an entity in a set of entities uniformly distributed in space is the nearest neighbor of its nearest neighbor is evaluated for generic distances in a multidimensional environment. Such an expression is then specialized for systems with norm-based distances and for systems with quantized norm- based distance. Examples for scalar products and sup-norm are derived. When applicable, invariances with respect to the underlying distance and entities density are highlighted. Dimensionality effects are investigated.