Totally bounded metric spaces and similarity detecting algorithms

摘要

Many questions of theoretical computer science can be reduced to the following problem: let$mathcal{X} = leftlangle {X,arrho } ightangle $ 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 $arrho (a,x) leq arepsilon $. This problem is called the similarity detecting problem of $(mathcal{X},A,arepsilon )$. 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.