Encontrar o par mais próximo entre dois conjuntos de pontos no hipercubo

Dados dois subconjuntos do hipercúbica -dimensional (isto é, ), Eu estou procurando um algoritmo que recupera os pontos r a distância de Hamming (ou - distância no hipercubo) é mínima. O algoritmo ingênuo que verifica apenas cada par precisa $d$ $M, N \subseteq \{0,1\}^d$ $m\in M, n\in N$ $L_1$ $d_H(m,n)$ $|M|\cdot |N| \cdot d$ tempo, há algum resultado melhor conhecido?

Por simplicidade, podemos assumir que . $|M|=|N|=d$

cg.comp-geom HdM
fonte

hmmm. existe mais motivação / aplicação? suspeito que exista um análogo multidimensional desse algoritmo euclidiano / planar, mas a wikipedia não cita nada e nunca ouviu falar dele em outro lugar ... pode ajudar a procurar um algoritmo para vetores n-dim. o início do artigo parece afirmar que pode ser resolvido em

para dimensões mais altas

mas não cita. talvez em algum lugar nos árbitros?

O (n \log n)

$O(n \log n)$

d > 2

$d>2$

vzn

O argumento de dividir e conquistar depende de um limite de empacotamento. Em dimensões mais altas, isso introduz um fator

na recorrência, mas a dependência de

permanece a mesma. Portanto, se você não se importa com termos exponenciais em

, pode usar esta abordagem. Se você quer algo exato, é improvável que consiga fazer melhor.

2^{d}

$2^d$

n

$n$

d

$d$

Suresh Venkat

veja também pesquisa de vizinhos mais próxima

vzn

Isso parece improvável. Pense nas seqüências aleatórias n + m no hipercubo. De alguma forma, a distância de hamming de cada par é aproximadamente d / 2, e você deve verificar todos os pares para encontrar o par mais próximo.

Sariel Har-Peled

@Sariel Har-Peled: Como Suresh escreveu, o problema pode ser resolvido no tempo O (n log n) (onde n = max {| M |, | N |}) para qualquer constante d. Portanto, “você precisa verificar todos os pares para encontrar o par mais próximo” não parece correto para mim.

Tsuyoshi Ito 03/02

Respostas:

$|M|=|N|=d$ $M$ $X$ $N$ $Y$ $Y$ $Z=XY$ $z_{i,j}$ $i$ $M$ $j$ $N$ $O(d^{2.3727})$ $O(d^{2.3726999999})$

Você pode obter um efeito semelhante se as matrizes não forem quadrados. Acho que Uri Zwick tem um artigo sobre multiplicação rápida de matrizes neste caso.

$O(|M| * |N|)$ $d$

Sariel Har-Peled
fonte

Ótima descoberta. Em outra nota, um colega meu encontrou este documento: toc.cse.iitk.ac.in/articles/v008a014/v008a014.pdf e só agora percebo que ele (também) foi escrito por você. Página 17+ é particularmente interessante ..

HDM

Sim. Parece familiar - de notar que esta é a aproximação - Suresh pediu o resultado exato ...

Sariel Har-Peled

-3

$L_\infty$ $L_m$ $L_1$ $O(dn \log n)$ $d$

[1] Um algoritmo ideal para pesquisa de vizinhos mais próximos aproximados em dimensões fixas Arya et al, 30pp

[2] Vizinhos mais próximos efetivos pesquisando no hipercubo, com aplicações em Cazals de agrupamento molecular

vzn
fonte

Ω (d^{d})

$\Omega(d^d)$