¿Por qué alguien usaría un Octree sobre un árbol KD?

32

Tengo cierta experiencia en informática científica, y he usado ampliamente kd-trees para aplicaciones BSP (partición de espacio binario). Recientemente me he familiarizado con los octrees, una estructura de datos similar para particionar espacios euclidianos en 3-D, pero que funciona a intervalos regulares fijos, por lo que deduzco.

Un poco de investigación de independencia parece indicar que los árboles kd son típicamente superiores en rendimiento para la mayoría de los conjuntos de datos, más rápidos de construir y consultar. Mi pregunta es, ¿cuáles son las ventajas de los octrees en el desempeño espacial / temporal o de otra manera, y en qué situaciones son más aplicables (he escuchado programación de gráficos 3D)? Un resumen de las ventajas y problemas de ambos tipos sería muy apreciado.

Como extra, si alguien pudiera dar más detalles sobre el uso de la estructura de datos del árbol R y sus ventajas, también lo agradecería. Los árboles R (más que los octreos) parecen aplicarse de manera bastante similar a los árboles kd para las búsquedas de k-vecino más cercano o rango.

Noldorin
fuente
Debo señalar que tanto los árboles kd como los árboles R (pero no los octreos) parecen diseñados específicamente para facilitar las búsquedas de vecinos más cercanos a k: ¿cómo se comparan en este sentido?
Noldorin
Una nota es que los árboles kd tienen una profundidad pequeña garantizada. Los árboles cuádruples comprimidos pueden llevarte allí, pero son menos convenientes.
Suresh Venkat
@Suresh Venkat: Gracias por eso. No estoy familiarizado con los quadtrees comprimidos, pero ¿serían realmente adecuados para repeticiones espaciales en 3-D? Tal vez hay un análogo "octree comprimido".
Noldorin
También he escuchado que los octrees son más apropiados cuando uno tiene una curva conocida de orden Z (relleno de espacio), pero no estoy muy seguro del razonamiento aquí.
Noldorin

Respuestas:

23

Las celdas en un árbol pueden tener una relación de aspecto alta, mientras que las celdas de octree tienen la garantía de ser cúbicas. Dado que este es un panel de teoría, le daré la razón teórica por la cual una alta relación de aspecto es un problema: hace que sea imposible usar límites de volumen para controlar el número de celdas que debe examinar al resolver consultas vecinas más cercanas.kD

Más detalladamente: si solicita un vecino más cercano aproximado a un punto de consulta q , y el vecino más cercano real está a la distancia d , generalmente termina con una búsqueda que examina cada celda de estructura de datos que llega desde el interior al fuera de un anillo o capa anular con radio interno d y radio externo ( 1 + ϵ ) d . Si las celdas tienen una relación de aspecto acotada, como están en un quadtree, entonces puede haber como máximo 1 / ϵ d - 1 de esas celdas, y puede probar buenos límites en el tiempo para la consulta. Si la relación de aspecto no está acotada, como en una kϵqdd(1+ϵ)d1/ϵd1 -tree, estos límites no se aplican.kD

árboles D tienen una ventaja diferente sobre los árboles cuádruples, ya que se garantiza que tienen una profundidad logarítmica máxima, lo que también contribuye al tiempo para una consulta de vecino más cercano. Pero la profundidad de un quadtree es como máximo el número de bits de precisión de la entrada que generalmente no es grande, y existen métodos teóricos para controlar que la profundidad sea esencialmente logarítmica (ver la estructura de datos omitir quadtree).kD

David Eppstein
fuente
44
Consulte el libro de texto reciente de Sariel Har-Peled para obtener un resumen moderno de cuadrantes comprimidos.
Jeffε
Gracias por un buen resumen cuantitativo, David. Solo para confirmar: ¿su uso de "relación de aspecto" es sinónimo de "relación de ramificación"? Definitivamente tendré que registrarme en omitir cuadrúpedos / octreos y quizás también en cuadrúpedos / octrees comprimidos.
Noldorin
1
La relación de aspecto de un cuadro rectangular se puede definir como la relación de su longitud de borde más larga a su longitud de borde más corta. No sé qué se supone que significa la relación de ramificación en este contexto, pero la relación de aspecto no está relacionada con el factor de ramificación de los árboles (que es constante para ambas estructuras de datos).
David Eppstein
Eché de menos las "celdas". Tiene sentido ahora.
Noldorin
15

Un grupo de amigos y yo estamos trabajando en un juego de estrategia en tiempo real como un divertido proyecto paralelo. Estamos usando muchas de las cosas que hemos aprendido en Ciencias de la Computación para hacerlo altamente eficiente, lo que nos permite hacer ejércitos masivos más adelante.

Para este propósito, hemos considerado usar kd-trees, pero los descartamos rápidamente: las inserciones y eliminaciones son extremadamente comunes en nuestro programa (considere una nave volando por el espacio), y este es un desastre impío con kd-trees. Por lo tanto, elegimos octrees para nuestro juego.

Alex ten Brink
fuente
Ah sí, también he escuchado esto antes. La inserción / eliminación con kd-trees es una operación costosa (debido al reequilibrio). Sin embargo, creo que las complejidades de tiempo del mejor de los casos siguen siendo las mismas ...
Noldorin
2
Depende de cómo se arregla el árbol kd. Una buena complejidad de tiempo en el mejor de los casos no es algo a lo que generalmente apunto: por ejemplo, bogosort tiene una O (1) complejidad en el mejor de los casos, pero espero que nadie la use.
Alex ten Brink
Desafortunadamente, parece que no puedo encontrar ningún buen resumen de las complejidades de tiempo para operaciones comunes en estas estructuras de datos, pero no me importa. La complejidad del tiempo promedio del caso a menudo es perspicaz ...
Noldorin
1
Realmente creo que aún lo harías mejor si solo usaras un árbol KD que ciclara los ejes y simplemente dividiera el espacio en el medio. Omita el voluminoso SAH y otros cortes medios caros y terminará con algo que no solo busca más rápido que un octree sino que también se desarrolla más rápido. Dado que está dividiendo el espacio de manera uniforme como lo haría con un octree, pero con un árbol binario en lugar de un árbol de 8 arios, lo que sea que haya hecho antes para eliminar no debería ser más complejo con el árbol KD, ya que Estarán espaciados uniformemente de manera similar. Ej: simplemente puede eliminar nodos vacíos más allá de una profundidad de N.
Dragon Energy
8

¿Cuáles son las ventajas de los octrees en el rendimiento espacial / temporal o de otra manera, y en qué situaciones son más aplicables (he escuchado programación de gráficos 3D)?

Los árboles kD son árboles binarios balanceados y los octrees son intentos por lo que las ventajas y desventajas probablemente se hereden de esas estructuras de datos más generales. Específicamente:

  • El reequilibrio puede ser costoso (los octrees no necesitan reequilibrar).
  • El equilibrio maneja mejor la heterogeneidad porque es adaptativa.
  • Un mayor factor de ramificación en los octreos significa árboles menos profundos (menos indirecciones y asignaciones) para distribuciones homogéneas.

Además, la bisección (como en los octrees) se presta a una implementación trivial en términos de giro de bits. Del mismo modo, imagino que los octrees pueden beneficiarse enormemente de las distancias precalculadas cuando realizan búsquedas de rango.

EDITAR

Al parecer, mis referencias a los intentos y la homogeneidad necesitan aclaración.

Los intentos son una familia de estructuras de datos representadas por árboles de diccionarios y se usan como diccionarios para claves que son secuencias (especialmente cadenas pero también secuencias de ADN y los bits en un valor hash para intentos hash). Si cada diccionario mapea un bit de cada una de las coordenadas x, y y z (el bit más significativo en el primer nivel del trie, el siguiente bit significativo en el segundo nivel, etc.), entonces el trie es un octree que subdivide uniformemente el espacio 3D. Por lo tanto, los octrees heredan las características de los intentos que son, en general:

  • Un alto factor de ramificación puede significar árboles poco profundos que incurren en pocas indirecciones, por lo que la búsqueda es rápida, por ejemplo, se pueden almacenar 20 niveles de árbol binario en 4 niveles de un árbol con un factor de ramificación de 256.
  • Los intentos no se reequilibran durante las inserciones y eliminaciones, lo que ahorra una operación costosa requerida para árboles binarios equilibrados.

La desventaja es que la heterogeneidad puede dar lugar a intentos / octrees desequilibrados, por lo que las búsquedas pueden requerir muchas indirecciones. El problema equivalente en los intentos se resuelve utilizando la compresión de bordes para colapsar múltiples niveles de indirección en un solo nivel. Los octrees no hacen esto, pero no hay nada que te impida comprimir un octree (¡pero no creo que puedas llamar al resultado octree!).

A modo de comparación, considere un diccionario especializado para claves de cadena que se representa como un trie. El primer nivel del trie se ramifica en el primer personaje de la clave. El segundo nivel en el segundo personaje y así sucesivamente. Se puede buscar cualquier cadena buscando el primer carácter de la clave en el diccionario para obtener un segundo diccionario que se utiliza para buscar el segundo carácter de la clave y así sucesivamente. Un conjunto de cadenas de teclas aleatorias sería una distribución homogénea . Un conjunto de cadenas clave que comparten un prefijo (por ejemplo, todas las palabras que comienzan con "anti") son heterogéneasdistribución. En el último caso, el primer diccionario contiene solo un enlace, para "a", el segundo solo para "n" y así sucesivamente. La búsqueda de cualquier mapeo en el trie siempre se realiza buscando los mismos cuatro diccionarios con las mismas cuatro teclas. Esto es ineficiente y esto es lo que hacen los octrees si, por ejemplo, se utilizan para almacenar distribuciones de partículas heterogéneas donde la gran mayoría de las partículas se encuentran en un pequeño volumen dentro del espacio vectorial.

Jon Harrop
fuente
"los octrees son intentos"? Además, ¿qué quiere decir con "maneja mejor la heterogeneidad"? Homogéneo no es una palabra que he encontrado con respecto a los árboles.
Noldorin
2
¿"Octtrees no necesita reequilibrar"? Eso no es absolutamente cierto para los octtrees que almacenan distribuciones puntuales heterogéneas. Alternativamente, dependiendo de cuán generalmente defina "octtree": reequilibrar un octtree es simplemente imposible , no importa cuán deseable pueda ser.
Jeffε
@Noldorin "los octrees son intentos". Sí. ¿Sabes qué es un trie? en.wikipedia.org/wiki/Trie
Jon Harrop
@Noldorin "Homogéneo no es una palabra que he encontrado con respecto a los árboles". Me refiero a la homogeneidad de la distribución que se está dividiendo. Por ejemplo, al dividir partículas en un espacio 3D, los átomos en un sólido se distribuyen de manera homogénea, mientras que las estrellas en el universo se distribuyen de manera heterogénea. Es más probable que los árboles kD sean preferibles para distribuciones heterogéneas porque su subdivisión del espacio es adaptativa.
Jon Harrop
@ Jɛ ff E "Reequilibrar un octtree es simplemente imposible". Eso es exactamente a lo que me refería. Disculpas si mi redacción era confusa.
Jon Harrop
2

Los octrees son útiles como un tipo de datos base para modelos continuos, ver por ejemplo el solucionador de flujo Gerris . La vida es bastante difícil en la dinámica de fluidos, por lo que saber que el tamaño de todos sus subcubos depende solo de su profundidad debe ser un factor simplificador.

Advertencia: ¡no soy un dinámico dinámico!

jjg
fuente
Interesante. Definitivamente puedo apreciar que los octrees son más fáciles de trabajar en modelos continuos ... Sin embargo, me pregunto cuál es el motivo de la programación de gráficos.
Noldorin