Digamos que tengo 1 millón de elipsoides N dimensionales de forma arbitraria y arbitrariamente orientados dispersos aleatoriamente a través del espacio N-dimensional. Dado un subconjunto de elipsoides, quiero "rápidamente" determinar el conjunto de todos los elipsoides que intersectan los elipsoides del primer conjunto.Algoritmo de intersección de los elipsoides rápidos
Tiene que haber un algoritmo para esto. ¿Qué es? ¿Cuál es su complejidad "O"?
La complejidad "O" sufre de la maldición de dimensionalidad si está permitiendo datos en N dimensiones. (Consulte this wikipedia article para obtener más información al respecto). Recomiendo préstamos de simulación física y dividiendo este problema en una "fase amplio" y una fase estrecho:
La fase estrecha es un problema directo de geometría computacional de prueba de intersección entre elipses arbitrarias. Para la fase amplia, querrá usar una estructura espacial, como un hash espacial, un árbol espacial (árbol-R, árbol-K, árbol-X, árbol-UB, etc.), o una estructura ad-hoc dada algunas propiedades especiales de los datos que está cargando (como un árbol desordenado o hash).
El método popular actual es un árbol Kd. Hay una gran cantidad de documentación y versiones ya codificadas del árbol de Kd que son fácilmente configurables, por lo que te recomiendo que busques en línea. (Google es tu amigo en este caso). La ventaja de utilizar la mayoría de las estructuras de árbol es que si el conjunto con el que estás buscando intersecciones es relativamente compacto, puedes buscar a través del árbol solo una vez y encontrar las intersecciones sin tener que realizar múltiples recorridos de árbol . Esto ayudará con los patrones de acceso a la memoria caché (ya sea desde la memoria principal o el disco). El mismo algoritmo puede manejar consultas de miembros dispares. Sin embargo, es probable que esté haciendo un trabajo que se beneficiaría enormemente de las propiedades de conjuntos de consultas compactos.
Un Kd-tree no solucionará sus problemas para todos los elipsoides, por ejemplo, si tiene un elipsoide de dimensión N cuyo eje primario es de (0, 0, 0, 0, ...) a través (1, 1, 1, 1, ...), pero con ejes secundarios pequeños o inconsecuentes (y en lo sucesivo no se cruzan mucho) todavía necesitará ser un nodo que cubra [0,1] en todas las N dimensiones. Si sus elipsoides caen en [0,1]^n, entonces cada elipsoide probará la intersección con el elipsoide inconveniente antes mencionado. Sin embargo, con datos del mundo real (e incluso la mayoría de los sintéticos, a menos que realmente se esfuercen por hacer que los árboles KD sean lentos), el enfoque del árbol KD debería ser una ganancia.
Si espera que Kd-tree sea un éxito para los elipsoides de miles de dimensiones, es probable que esté mejor con una búsqueda de fuerza bruta. (La maldición de dimensionalidad antes mencionada). Sin embargo ...
Un millón de entradas no es tan malo si tienes una implementación optimizada, pero si estás haciendo un montón de consultas (millones) va a ser lento (del orden de 10 segundos o peor). Sin embargo, he visto algunos números increíbles a partir de un código vectorizado bien optimizado. (Incluso envió algunos productos usando esta estrategia.) Con la coherencia de caché adecuada, la fuerza bruta solo tomaría milisegundos como máximo. Esto significa ASM o vectores intrínsecos en C/C++: no estoy seguro de en qué idioma está trabajando.
Para la mayoría de los datos, la complejidad O (sin tener en cuenta la maldición de la dimensionalidad) debe ser amortiguada O (m log n) para consultas (una vez que se construye el árbol) donde m es el número de elipses en el conjunto de consultas yn es el número de elipses en el conjunto de datos.La construcción de los datos en sí no debería ser peor que O (n log n). Multiplique todo por Exp (d) donde d es la dimensión: así es como funciona este tipo de cosas.
¡Fascinante! Gracias por la aportación. Así que mi mensaje para llevar es que, si puedo hacer algunas suposiciones sobre el tamaño máximo de los elipsoides, entonces puedo usar un árbol Kd para sacrificar rápidamente el espacio a un tamaño que sea más manejable para el problema de la geometría computacional de la fuerza bruta . – JnBrymn
Esencialmente sí. Y si realmente lo necesita debido a restricciones de espacio, puede hacerlo desde el disco, ya que el cruce de árbol depende mucho menos del ancho de banda que la fuerza bruta. Pero una solución de fuerza bruta bien optimizada (si se debe a eso debido a requisitos que no conozco aquí) aún puede funcionar. De hecho, he enviado juegos de ese tipo de fuerza bruta similares tipos de problemas en unos pocos milisegundos por cuadro, pero eso fue una gran optimización cuidadosa. – Kaganar
Si no desea utilizar una implementación de árbol Kd previamente enrollado y prefiere utilizar su propia estructura, si los elipsoides son de tamaño bastante uniforme, una estructura de hash espacial es mucho más fácil de implementar y puede tener algunos superiores el rendimiento depende de los datos en sí. Los árboles de KD generalmente son más agnósticos a los datos, pero tienen operaciones más complejas que los ralentizan. Ambos son muy sensibles a la dimensionalidad. – Kaganar
¿Por qué? Sin el por qué, huele a "haz las tareas para mí". – spender
¿Podemos suponer que sus elipsoides están almacenados en algún tipo de estructura de datos similar a un árbol, como el equivalente en N dimensiones de un árbol cuádruple? Si no, entonces esto es más o menos un problema * O (MN) *, donde * M * es el tamaño del subconjunto, y * N * es el tamaño del conjunto. –
@spender - ¡excelente! Eso significa que la respuesta será fácil de conseguir. El motivo es porque quiero vincular distribuciones de probabilidad arbitrarias usando familias de esferas. Determinar qué familia de esferas se superpone me permitirá hacer un primer corte para resolver un problema de probabilidad generalizada. - No, esto no es un problema de tarea. – JnBrymn