Error Probability for Scalar Neural Network Trees in High-Dimensional Binary Space

Regular price $0.00 Sale

8th International Conference on Bio-inspired Information and Communications Technologies (formerly BIONETICS)
Irina Zhelavskaya1, Vladimir Kryzhanovsky1, Magomed Malsagov1
1: Scientific Research Institute for System Analysis, Russian Academy of Sciences

    The paper investigates SNN-tree algorithm that extends the binary search tree algorithm so that it can deal with distorted input vectors. Unlike the SNN-tree algorithm, popular methods (LSH, k-d tree, BBF-tree, spill-tree) stop working as the dimensionality of the space grows (N > 1000). The proposed algorithm works much faster than exhaustive search (26 times faster at N=10000). However, some errors may occur during the search. In this paper we managed to obtain an estimate of the upper bound on the error probability for SNN-tree algorithm. In case when the dimensionality of input vectors is N≥500 bits, the probability of error is so small (P<10-15) that it can be neglected according to this estimate and experimental results. In fact, we can consider the proposed SNN-tree algorithm to be exact for high dimensionality (N ≥ 500).