On Error Probability of Search in High-Dimensional Binary Space with Scalar Neural Network Tree

Vladimir Kryzhanovsky, Magomed Malsagov, Juan Antonio Clares Tomas, Irina Zhelavskaya

2014

Abstract

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).

Paper Citation

in Harvard Style

Kryzhanovsky V., Malsagov M., Clares Tomas J. and Zhelavskaya I. (2014). On Error Probability of Search in High-Dimensional Binary Space with Scalar Neural Network Tree . In Proceedings of the International Conference on Neural Computation Theory and Applications - Volume 1: NCTA, (IJCCI 2014) ISBN 978-989-758-054-3, pages 300-305. DOI: 10.5220/0005152003000305

in Bibtex Style

@conference{ncta14,
author={Vladimir Kryzhanovsky and Magomed Malsagov and Juan Antonio Clares Tomas and Irina Zhelavskaya},
title={On Error Probability of Search in High-Dimensional Binary Space with Scalar Neural Network Tree},
booktitle={Proceedings of the International Conference on Neural Computation Theory and Applications - Volume 1: NCTA, (IJCCI 2014)},
year={2014},
pages={300-305},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005152003000305},
isbn={978-989-758-054-3},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Neural Computation Theory and Applications - Volume 1: NCTA, (IJCCI 2014)
TI - On Error Probability of Search in High-Dimensional Binary Space with Scalar Neural Network Tree
SN - 978-989-758-054-3
AU - Kryzhanovsky V.
AU - Malsagov M.
AU - Clares Tomas J.
AU - Zhelavskaya I.
PY - 2014
SP - 300
EP - 305
DO - 10.5220/0005152003000305