Encontrar el par más cercano entre dos conjuntos de puntos en el hipercubo

Dados dos subconjuntos del hipercubo dimensional (es decir, ), estoy buscando un algoritmo que recupere los puntos st la distancia de Hamming (o - distancia en el hipercubo) es mínima. El ingenuo algoritmo que verifica cada par necesita $d$ $M, N \subseteq \{0,1\}^d$ $m\in M, n\in N$ $L_1$ $d_H(m,n)$ $|M|\cdot |N| \cdot d$ tiempo, ¿hay algún resultado mejor conocido?

Por simplicidad, podemos suponer que . $|M|=|N|=d$

cg.comp-geom HdM
fuente

hmmm ¿Hay más motivación / aplicación? sospecha que hay un análogo multidimensional de este algoritmo euclidiano / plano, pero wikipedia no cita nada y no ha oído hablar de él en otro lugar ... podría ayudar a buscar un algoritmo para vectores n-dim. El comienzo del artículo parece afirmar que se puede resolver en

para dimensiones superiores

pero no da ninguna cita. tal vez en algún lugar de los árbitros?

O (n \log n)

$O(n \log n)$

d > 2

$d>2$

vzn 01 de

El argumento de dividir y conquistar se basa en un límite de embalaje. En dimensiones superiores, esto introduce un factor

en la recurrencia, pero la dependencia de

sigue siendo la misma. Entonces, si no le importan los términos exponenciales en

, puede usar este enfoque. Si quieres algo exacto, es poco probable que puedas hacerlo mejor.

2^{d}

$2^d$

n

$n$

d

$d$

Suresh Venkat

ver también búsqueda de vecino más cercano

vzn

Esto parece poco probable. Piense en n + m cadenas aleatorias en el hipercubo. De alguna manera, la distancia de hamming de cada par es aproximadamente d / 2, y debe verificar todos los pares para encontrar el par más cercano.

Sariel Har-Peled

@Sariel Har-Peled: Como escribió Suresh, el problema puede resolverse en el tiempo O (n log n) (donde n = max {| M |, | N |}) para cualquier constante d. Por lo tanto, "tienes que verificar todos los pares para encontrar el par más cercano" no me parece correcto.

Tsuyoshi Ito

Respuestas:

Me acabo de dar cuenta de que estás pidiendo el caso de que . Entonces puedes hacer multiplicación de matrices, ¿verdad? Comentario es una matriz fila , como una matriz de la columna , niega las entradas de , y calcular la matriz . Claramente, la es la distancia de Hamming entre el punto de y el punto de $|M|=|N|=d$ $M$ $X$ $N$ $Y$ $Y$ $Z=XY$ $z_{i,j}$ $i$ $M$ $j$ $N$ . De acuerdo con los últimos avances, esto tiene un tiempo de ejecución (pero tengo un manuscrito de 50,000 páginas que muestra cómo hacer esta multiplicación de matriz en tiempo por un algoritmo realmente simple). $O(d^{2.3727})$ $O(d^{2.3726999999})$

Puede obtener un efecto similar si las matrices no son cuadrados. Creo que Uri Zwick tiene un artículo sobre la multiplicación rápida de matrices en este caso.

En cierto sentido, esto no es demasiado interesante: queremos evitar el término . Las mejoras en el término son como meh, meh ... $O(|M| * |N|)$ $d$

Sariel Har-Peled
fuente

Gran hallazgo. En otra nota, un colega mío encontró este documento: toc.cse.iitk.ac.in/articles/v008a014/v008a014.pdf y solo ahora me doy cuenta de que fue (también) escrito por usted. La página 17+ es particularmente interesante ..

HdM

Si. Parece familiar, pero tenga en cuenta que esto es una aproximación. Suresh pidió el resultado exacto ...

Sariel Har-Peled

-3

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

[1] Un algoritmo óptimo para la búsqueda del vecino más cercano aproximado en dimensiones fijas Arya et al, 30pp

[2] Vecinos más cercanos efectivos que buscan en el hipercubo, con aplicaciones a Cazals de agrupamiento molecular

vzn
fuente

Ω (d^{d})

$\Omega(d^d)$