Une structure de données pour les requêtes minimales sur les produits scalaires

Considérez équipé du produit scalaire standard et vecteurs: . Nous voulons construire une structure de données qui autorise les requêtes au format suivant: étant donné output . Est-il possible d'aller au-delà du temps de requête O (nm) trivial ? Par exemple, si n = 2 , alors il est immédiat d'obtenir O (\ log ^ 2 m) .$\mathbb{R}^n$$\langle \cdot, \cdot \rangle$$m$$v_1, v_2, \ldots, v_m$$x \in \mathbb{R}^n$$\min_i \langle x, v_i \rangle$$O(nm)$$n = 2$$O(\log^2 m)$

La seule chose que je peux trouver est la suivante. C'est une conséquence immédiate du lemme de Johnson-Lindenstrauss que pour chaque $\varepsilon > 0$ et une distribution $\mathcal{D}$ sur $\mathbb{R}^n$ il y a un mappage linéaire $f \colon \mathbb{R}^n \to \mathbb{R}^{O(\log m)}$ (qui peut être évalué en $O(n \log m)$ temps) de telle sorte que $\mathrm{Pr}_{x \sim \mathcal{D}}\left[\forall i \quad \langle x, v_i \rangle - \varepsilon (\|x\| + \|v_i\|)^2 \leq \langle f(x), f(v_i)\rangle \leq \langle x, v_i \rangle + \varepsilon (\|x\| + \|v_i\|)^2 \right] \geq 1 - \varepsilon$ . Donc, dans le temps $O((n + m) \log m)$ nous pouvons calculerquelque chose qui est en quelque sorte proche de $\min_i \langle x, v_i \rangle$ pour la plupart des $x$ (au moins si les normes $\|x\|$ et $\|v_i\|$ sont petites).

UPD La limite susmentionnée peut être quelque peu affinée au temps de requête $O(n + m)$ si nous utilisons un hachage sensible à la localité. Plus précisément, nous choisissons $k := O(\frac{1}{\varepsilon^2})$ des vecteurs gaussiens indépendants $r_1, r_2, \ldots, r_k$ . Ensuite, nous mappons $\mathbb{R}^n$ à $\{0,1\}^k$ comme suit: $v \mapsto (\langle r_1, v \rangle \geq 0, \langle r_2, v \rangle \geq 0, \ldots, \langle r_k, v \rangle \geq 0)$ . On peut alors estimer l'angle entre deux vecteurs au sein d'une erreur additive $\varepsilon$ en calculant $\ell_1$ -distance dans l'image de cette cartographie. Ainsi, nous pouvons estimer les produits scalaires au sein d'une erreur additive$\varepsilon \|x\| \|v_i\|$en temps $O(\frac{1}{\varepsilon^2})$ .

Considérez le cas spécial où vous voulez simplement déterminer si votre vecteur de requête est orthogonal à un vecteur de votre collection prétraité. (Autrement dit, vous voulez déterminer si , où les vecteurs en discussion ont des coefficients non négatifs.) Ce cas est déjà très intéressant.$\min_i \langle x, v_i \rangle = 0$

Supposons que vous puissiez répondre aux requêtes en temps pour un certain , avec prétraitement (le les degrés du polynôme ne devraient pas dépendre de ou ou ).n O ( 1 ) m 1 - δ δ > 0 m O ( 1 ) n O ( 1 ) m n $n^{O(1)} m^{1-\delta}$$\delta > 0$$m^{O(1)} n^{O(1)}$$m$$n$$\delta$

Dans l'article "Un nouvel algorithme pour une satisfaction optimale des contraintes 2 et ses implications", j'ai observé qu'une telle structure de données vous permettrait en fait de résoudre CNF-SAT en temps pour un certain , où est le nombre de variables. Cela réfuterait la "forte hypothèse exponentielle temporelle" selon laquelle k-SAT nécessite essentiellement temps pour non borné .2 α v α < 1 v 2 n$2^{\alpha v}$$\alpha < 1$$v$$2^n$$k$

Pour voir pourquoi, supposons que le temps de prétraitement est limité par . Considérons une formule CNF avec variables et clauses. Nous divisons l'ensemble de variables en deux parties et de taille et , respectivement. Répertoriez toutes les affectations possibles aux variables dans les parties (obtention des affectations et , respectivement). Associez chacune de ces affectations partielles à un vecteur à bits où si$(nm)^c$$F$$v$$n$$P_1$$P_2$$v(1-1/(2c))$$v/(2c)$$2^{v(1-1/(2c))}$$2^{v/(2c)}$$A_i$$n$$w_i$$w_i[j]=1$$j$La clause de n'est pas satisfaite par . Nous avons donc deux listes de vecteurs de bits exponentiellement nombreux.$F$$A_i$

Notez que est satisfiable si il existe un vecteur d'une affectation sur et un vecteur d'une affectation sur tel que .$F$$w_1$$P_1$$w_2$$P_2$$\langle w_1, w_2 \rangle = 0$

Soit maintenant , et prétraitez la structure de données supposée avec tous les vecteurs de la partie . Cela prend temps, par hypothèse. Exécutez l'algorithme de requête sur tous les vecteurs à partir des affectations de la pièce . Par hypothèse, cela prend . Soit .$m=2^{v/(2c)}$$P_2$$n2^{v/2}$$P_1$$2^{v(1-1/(2c))} \cdot n^{O(1)} m^{1-\delta} = n^{O(1)} 2^{v - \delta v/(2c)}$$\alpha = 1 - \delta/(2c)$

Il est peut-être possible d'obtenir un prétraitement efficace et un temps de requête avec les techniques existantes. Les algorithmes CNF-SAT les plus connus ne l'excluent pas. (Ils obtiennent quelque chose comme .) Mais pour calculer est légèrement plus fort - dans cette configuration, ce serait comme résoudre MAX CNF-SAT.$n^{O(1)} m^{1-1/(\log \log m)}$$2^{n-n/\log n}$$\min_i \langle x, v_i\rangle$

Voici une idée de la réponse exacte à laquelle je pense que Chao Xu pourrait faire allusion. Observons tout d'abord que nous pourrions aussi bien normaliser , comme le souligne Chao. Considérons maintenant l'hyperplan normal à la direction . Le but est de trouver le point le plus proche de cet hyperplan. Par dualité, cela correspond à une requête de tir de rayon dans un arrangement d'hyperplans pour trouver le plan le plus proche "au-dessus" du point de requête. Étant donné que cela peut être prétraité, la principale complexité est l'emplacement du point, et donc votre problème a maintenant été réduit à la complexité de la localisation du point dans une disposition d'hyperplans. En utilisant des boutures, cela peut être fait en temps dans l' espace .$x$$h$$x$$O(\log n)$$n^d$