Uma estrutura de dados para consultas mínimas de produtos por pontos

19

Considere Rn equipado com os vetores de produto de ponto padrão e vetores: . Queremos construir uma estrutura de dados que permita consultas no seguinte formato: dado output . É possível ir além do tempo trivial de consulta de O (nm) ? Por exemplo, se n = 2 , é imediato obter O (\ log ^ 2 m) .,mv1,v2,,vmxRnminix,viO(nm)n=2O(log2m)

A única coisa que posso pensar é o seguinte. É uma consequência imediata do lema de Johnson-Lindenstrauss que, para todo e uma distribuição em exista um mapeamento linear de (que pode ser avaliado em ), de modo que . Então, no tempo O ((n + m) \ log m) podemos calcularε>0DRnf:RnRO(logm)O(nlogm)PrxD[ix,viε(x+vi)2f(x),f(vi)x,vi+ε(x+vi)2]1εO((n+m)logm)algo que está em algum sentido próximo de minix,vi para a maioria dos x 's (pelo menos se as normas x e vi forem pequenas).

UPD O limite acima mencionado pode ser um pouco mais aguçado para o tempo de consulta O(n+m) se usarmos o hash sensível à localidade. Mais precisamente, escolhemos k:=O(1ε2) vetores gaussianos independentes r1,r2,,rk . Em seguida, Rn para {0,1}k seguinte maneira: v(r1,v0,r2,v0,,rk,v0) . Então, podemos estimar o ângulo entre dois vetores dentro de um erro aditivo ε computando 1 -Distância na imagem deste mapeamento. Assim, podemos estimar produtos pontuais dentro de um erro aditivoεxvino tempo O(1ε2) .


ilyaraz
fonte
Não tenho certeza se isso funciona ou ajuda, mas seu problema (depois de alternar o sinal de v_i para converter para a maximização) parece relacionado aos diagramas de Voronoi. Pode ser possível modificar algoritmos para os diagramas de Voronoi para esse problema, mas mesmo se for possível, provavelmente será útil apenas para n pequeno.
Tsuyoshi Ito
Não sei se é a mesma observação ... Todo pode ser normalizado para um vetor de unidade e não altera o resultado, podemos fazer tudo em uma unidade n-cubo centrada na origem. Encontre qual região do cubo minimize o produto com para cada (cada região deve ser um politopo). Eu não tenho um limite para o número de politopos. Se for menor que exponencial em , você terá algo melhor que fazendo uma consulta de localização de ponto n-dimensional. xviinmO(nm)
Chao Xu
com qual parâmetro você se importa mais? normalmente, se você quiser ficar sublinear em m, começará a ficar exponencial em n.
Suresh Venkat
@ Suresh Bem, seria bom entender diferentes possíveis trocas. A versão aproximada também é interessante.
Ilyaraz 14/08
Nota rápida: para o caso n = 2, a pesquisa binária no casco convexo fornece tempo de consulta . O(logn)
Geoffrey Irving

Respostas:

16

Considere o caso especial em que você deseja determinar se seu vetor de consulta é ortogonal a algum vetor em sua coleção pré-processada. (Ou seja, você deseja determinar se , onde os vetores em discussão têm coeficientes não negativos.) Esse caso já é muito interessante.minix,vi=0

Suponha que você possa responder a consultas em tempo para alguns , com pré-processamento (o os graus do polinômio não devem depender de ou ou ).nO(1)m1δδ>0mO(1)nO(1)mnδ

No artigo "Um novo algoritmo para satisfação ideal com 2 restrições e suas implicações", observei que essa estrutura de dados realmente permitiria que você resolvesse o CNF-SAT em por algum tempo , onde é o número de variáveis. Isso refutaria a "Hipótese do tempo exponencial forte" de que o k-SAT requer essencialmente tempo para ilimitado .2αvα<1v2nk

Para entender por que, suponha que o tempo de pré-processamento seja limitado por . Considere uma fórmula CNF com variáveis cláusulas. Dividimos o conjunto de variáveis ​​em duas partes e de tamanho e , respectivamente. Liste todas as atribuições possíveis para as variáveis ​​nas partes (obtendo e atribuições, respectivamente). Associe cada uma dessas atribuições parciais com um vetor de bits que se(nm)cFvnP1P2v(11/(2c))v/(2c)2v(11/(2c))2v/(2c)Ainwiwi[j]=1jA cláusula de não é satisfeita por . Portanto, temos duas listas de vetores de bits exponencialmente numerosos.FAi

Observe que é satisfatório se houver um vetor de uma atribuição em e um vetor de uma atribuição em modo que .Fw1P1w2P2w1,w2=0

Agora deixe e pré-processe a estrutura de dados assumida com todos os vetores da parte . Isso leva tempo , por suposição. Execute o algoritmo de consulta em todos os vetores de atribuições na parte . Por suposição, isso leva . Seja .m=2v/(2c)P2n2v/2P12v(11/(2c))nO(1)m1δ=nO(1)2vδv/(2c)α=1δ/(2c)

Talvez seja possível obter pré-processamento eficiente e tempo de consulta com as técnicas existentes. Os algoritmos CNF-SAT mais conhecidos não descartam isso. (Eles obtêm algo como .) Mas, para calcular é um pouco mais forte - nessa configuração, seria como resolver o MAX CNF-SAT.nO(1)m11/(loglogm)2nn/lognminix,vi

Ryan Williams
fonte
Impressionante! Mas não descarta estruturas de dados aproximadas, bem como tempos de consulta como , o que também seria muito interessante. O(mpoly(logn))
Ilyaraz
A propósito, não podemos dizer algo como "se houvesse estrutura de dados aproximada com tempo de consulta rápido, o MAX-SAT seria aproximado".
Ilyaraz
Por que a equivalência declarada no primeiro parágrafo é válida? Eu acho que o produto interno pode ser negativo em geral.
Tsuyoshi Ito
ilyaraz: Sim, mesmo estruturas de dados aproximadas implicariam MAX-SAT aproximado. Tsuyoshi: Obrigado pela sua visão
Ryan Williams
6

Aqui está uma idéia para a resposta exata, à qual suspeito que Chao Xu possa estar se referindo. Em primeiro lugar, observe que podemos normalizar , como Chao aponta. Agora considere o hiperplano h normal na direção x . O objetivo é encontrar o ponto mais próximo desse hiperplano. Por dualidade, isso corresponde a uma consulta de disparo de raios em um arranjo de hiperplanos para encontrar o plano mais próximo "acima" do ponto de consulta. Como isso pode ser pré-processado, a principal complexidade é a localização do ponto e, portanto, seu problema foi reduzido à complexidade de fazer a localização do ponto em um arranjo de hiperplanos. Usando estacas, isso pode ser feito no tempo O ( log n ) em n dxhxO(logn)nd espaço.

Suresh Venkat
fonte
11
Eu deveria ter mencionado que também estou interessado em um tempo razoável de pré-processamento, o que não é o caso aqui se uma dimensão for grande.
Ilyaraz