Una estructura de datos para consultas mínimas de productos de puntos

19

Rn,mv1,v2,,vmxRnmin ix , v iminix,viO ( n m )O(nm) n = 2 n=2O ( conecto 2 m )O(log2m)

Lo único que se me ocurre es lo siguiente. Es una consecuencia inmediata del lema de Johnson-Lindenstrauss que por cada y una distribución \ mathcal {D} en \ mathbb {R} ^ n hay un mapeo lineal f \ colon \ mathbb {R} ^ n \ to \ mathbb {R} ^ {O (\ log m)} (que puede evaluarse en tiempo O (n \ log m) ) de modo 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 . Entonces, en el tiempo O ((n + m) \ log m) podemos calcularε > 0 ε>0D DR nRn f : R nR O ( log m )f:RnRO(logm)O ( n log m ) O(nlogm)P r x D [iX , v i- ε ( x + v i) 2f ( x ) , f ( v i ) x , v i+ ε ( x + v i) 2 ]1 - ε O ( ( nPrxD[ix,viε(x+vi)2f(x),f(vi)x,vi+ε(x+vi)2]1ε+ m ) log m )O((n+m)logm)algo que en cierto sentido está cerca de min ix , v iminix,vi para la mayoría de las Xx '(al menos si las normas X x y V ivi son pequeñas).

UPD El límite mencionado anteriormente se puede agudizar un poco al tiempo de consulta O ( n + m )O ( n + m ) si usamos hashing local. Más precisamente, elegimos k : = O ( 1ε 2 )k : = O ( 1ε2) vectores gaussianos independientes r 1 , r 2 , , r kr1, r2, ... , rk . Luego asignamos R nRnorte a { 0 , 1 } k{ 0 , 1 }k siguiente manera: v ( r 1 , v 0 , r 2 , v 0 , ... , r k , v 0 )v ( r1,v0,r2,v0,,rk,v0) . Luego podemos estimar el ángulo entre dos vectores dentro de un error aditivo εε calculando 11 -distancia en la imagen de este mapeo. Por lo tanto, podemos estimar productos puntuales dentro de un error aditivoε x v iεxvien O ( 1ε 2 )O(1ε2) tiempo.


ilyaraz
fuente
No estoy seguro de si esto funciona o ayuda, pero su problema (después de cambiar el signo de v_i para convertirlo a la maximización) parece estar relacionado con los diagramas de Voronoi. Es posible modificar algoritmos para diagramas de Voronoi a este problema, pero incluso si es posible, probablemente será útil solo para n pequeña.
Tsuyoshi Ito
No sé si esta es la misma observación ... Todo puede normalizarse a un vector unitario y no cambia el resultado, podemos hacer todo en una unidad n-cubo centrada en origen. Encuentre qué región del cubo minimiza el producto de puntos con para cada (cada región debe ser un politopo). No tengo un límite en el número de politopos. Si es menos que exponencial en , tiene algo mejor que haciendo una consulta de ubicación de punto n-dimensional. x v i i n m O ( n m )xviinmO(nm)
Chao Xu
¿Qué parámetro te interesa más? por lo general, si desea obtener sublineal en m, comenzará a obtener exponencial en n.
Suresh Venkat
@Suresh Bueno, sería bueno entender diferentes posibles compensaciones. La versión aproximada también es interesante.
ilyaraz
Nota rápida: para el caso n = 2, la búsqueda binaria en el casco convexo da tiempo de consulta . O ( log n )O(logn)
Geoffrey Irving

Respuestas:

16

Considere el caso especial en el que solo desea determinar si su vector de consulta es ortogonal a algún vector en su colección preprocesada. (Es decir, desea determinar si , donde los vectores en discusión tienen coeficientes no negativos). Este caso ya es muy interesante.minix,vi=0minix,vi=0

Suponga que puede responder consultas en tiempo durante algún , con preprocesamiento (el Los grados del polinomio no deberían depender de o o ).nO(1)m1δnO(1)m1δδ>0δ>0mO(1)nO(1)mO(1)nO(1)mmnnδδ

En el documento "Un nuevo algoritmo para la satisfacción óptima de 2 restricciones y sus implicaciones", observé que dicha estructura de datos realmente le permitiría resolver CNF-SAT en por algún tiempo , donde es el número de variables. Esto refutaría la "hipótesis del tiempo exponencial fuerte" que k-SAT requiere esencialmente tiempo para ilimitado .2αv2αvα<1α<1vv2n2nkk

Para ver por qué, suponga que el tiempo de preprocesamiento está limitado por . Considere una fórmula CNF con variables y cláusulas. Dividimos el conjunto de variables en dos partes y de tamaño y , respectivamente. Enumere todas las asignaciones posibles a las variables en las partes (obteniendo y asignaciones, respectivamente). Asociar cada una de estas asignaciones parciales con una( n m ) c F v n P 1 P 2 v ( 1 - 1 / ( 2 c ) ) v / ( 2 c ) 2 v ( 1 - 1 / ( 2 c ) ) 2 v / ( 2 c ) A i norte(nm)cFvnP1P2v(11/(2c))v/(2c)2v(11/(2c))2v/(2c)Ain vector de bits w i donde w i [ jwi] = 1 si lacláusula j ésima de F no es satisfecha por A i . Entonces tenemos dos listas de exponencialmente muchos vectores de bits.wi[j]=1jFAi

Tenga en cuenta que F es si y sólo si satisfiable existe un vector w 1 de una misión en P 1 y un vector w 2 de una misión en P 2 de tal manera que w 1 , w 2= 0 .Fw1P1w2P2w1,w2=0

Ahora dejemos que m = 2 v / ( 2 c ) , y preprocese la estructura de datos supuesta con todos los vectores de la parte P 2 . Esto toma n 2 v / 2 tiempo, por supuesto. Ejecute el algoritmo de consulta en todos los vectores desde las asignaciones de la parte P 1 . Suponiendo que esto toma 2 v ( 1 - 1 / ( 2 c ) )n O ( 1 ) m 1 - δ = nm=2v/(2c)P2n2v/2P1O ( 1 ) 2 v - δ v / ( 2 c ) . Seaα=1-δ / (2c).2v(11/(2c))nO(1)m1δ=nO(1)2vδv/(2c)α=1δ/(2c)

Quizás sea posible obtener un preprocesamiento eficiente y n O ( 1 ) m 1 - 1 / ( log log m ) tiempo de consulta con las técnicas existentes. Los algoritmos CNF-SAT más conocidos no lo descartan. (Consiguen algo así como 2 n - n / log n ). Pero para calcular min ix , v i es ligeramente más fuerte - en esta configuración, sería como resolver MAX CNF-SAT.nO(1)m11/(loglogm)2nn/lognminix,vi

Ryan Williams
fuente
¡Increíble! Pero no descarta estructuras de datos aproximadas, así como tiempos de consulta como O ( m p o l y ( log n ) ) , que también sería muy interesante. O(mpoly(logn))
ilyaraz
Por cierto, no podemos decir algo como "si hubiera una estructura de datos aproximada con un tiempo de consulta rápido, entonces MAX-SAT sería aproximable".
ilyaraz
¿Por qué es válida la equivalencia establecida en el primer párrafo? Creo que el producto interno puede ser negativo en general.
Tsuyoshi Ito
ilyaraz: Sí, incluso las estructuras de datos aproximadas implicarían un MAX-SAT aproximado. Tsuyoshi: Gracias por su comprensión
Ryan Williams
6

Aquí hay una idea para la respuesta exacta, que sospecho que Chao Xu podría estar aludiendo. En primer lugar, observe que también podríamos normalizar x , como señala Chao. Ahora considere el hiperplano h normal a la dirección x . El objetivo es encontrar el punto más cercano a este hiperplano. Por dualidad, esto corresponde a una consulta de disparo de rayos en una disposición de hiperplanos para encontrar el plano más cercano "encima" del punto de consulta. Como esto puede ser preprocesado, la complejidad principal es la ubicación del punto, por lo que su problema ahora se ha reducido a la complejidad de hacer la ubicación del punto en una disposición de hiperplanos. Usando esquejes, esto se puede hacer en tiempo O ( log n ) en n dxhxO(logn)nd espacio.

Suresh Venkat
fuente
1
Debería haber mencionado que también estoy interesado en un tiempo de preprocesamiento razonable, que no es el caso aquí si una dimensión es grande.
ilyaraz