Нахождение похожих векторов в субквадратичном времени

Позволять $d:\{0,1\}^k\times \{0,1\}^k \to \mathbb{R}$быть функцией, которую мы называем функцией подобия . Примерами функции подобия являются косинусное расстояние,$l_2$ норма, расстояние Хэмминга, сходство Жакара и т. д.

Рассматривать $n$ двоичные векторы длины $k$: $\vec{v} \in (\{0,1\}^k)^n$,

Наша цель - сгруппировать векторы, которые похожи. Более формально, мы хотим вычислить граф подобия, где узлы - это векторы, а ребра - векторы, которые похожи ($d(v,u) \leq \epsilon$).

$n$ а также $k$ очень большие числа, и сравнивая две длины $k$ векторы дорогие, мы не можем сделать всю грубую силу $O(n^2)$операции. Мы хотим вычислить граф подобия с существенно меньшим количеством операций.

Это возможно? Если нет, мы можем вычислить приближение к графу, которое содержит все ребра в графе подобия плюс, возможно, самое большее$O(1)$ другие края?

Там может быть способ вставить теорему Джонсона-Линденштраусса в эту проблему. По сути, JL заявляет, что вы можете проецировать данные больших размеров в пространства меньших размеров таким образом, что попарные расстояния почти сохраняются. С практической точки зрения, у Ахлиоптаса есть статья под названием « Случайные проекции , удобные для баз данных»: Джонсон-Линденштраусс с бинарными монетами, которая делает эту проекцию случайным образом, что довольно хорошо работает на практике.

Теперь, конечно, ваша функция подобия не совсем совпадает с той, что вписывается в теорему JL. Тем не менее, это похоже на функцию расстояния, и, возможно, некоторые из приведенных выше теорий могут помочь.