Totally bounded metric spaces and similarity detecting algorithms
Gábor Sági, Karrar Al-Sabti · 2019
Many questions of theoretical computer science can be reduced to the following problem: let$\mathcal{X} = \left\langle {X,\varrho } \right\rangle $ be a metric space, let $A \subseteq X$ and let ε be a positive real number; for a given input $x \in X$ find $a \in A$ (if any) for which $\varrho (a,x) \leq \varepsilon $. This problem is called the similarity detecting problem of $(\mathcal{X},A,\varepsilon )$. Usually, A (or sometimes X) is finite but huge, and the challenge is to represent the metric space in such a way computer algorithms may handle it efficiently.Based on recent results of [9] we propose a similarity detecting algorithm. We associate a finite dimensional Euclidean space $\mathcal{Y}$ to $\mathcal{X}$ and an "almost isometry" f : X → Y which preserve distances modulo a controlled amount of inaccuracy. After that, instead of working with $\mathcal{X}$, we can work with $\mathcal{Y}$. The main result of this work is the description of the above method.In the special case, when $\mathcal{X}$ itself is a large dimensional Euclidean space (with its usual Euclidean metric), our method can be considered as a kind of dimension reduction. In this special case we are analyzing the time complexity of our proposed algorithm, as well.