valores - seleccionar varios atributos en arcgis
Estructura de datos espaciales rápidos para la búsqueda de vecinos más cercanos entre hiperesferas de tamaño no uniforme (2)
Esperaría que un QuadTree / Octree / generalizado a 2 ^ K-tree para su dimensionalidad de K haría el truco; estos espacios de partición recursiva, y presumiblemente pueden detenerse cuando un subcubo K (o un bloque K-rectangular si las divisiones no son pares) no contiene una hiperesfera, o contiene una o más hiperesferas de manera que el particionamiento no separa ninguna, o alternativamente contiene el centro de una sola hiperesfera (probablemente más fácil).
Insertar y eliminar entidades en dichos árboles es rápido, por lo que un tamaño cambiante de hiperesfera solo causa un par de operaciones de eliminar / insertar. (Sospecho que puedes optimizar esto si el tamaño de tu esfera cambia por partición recursiva adicional local si la esfera se hace más pequeña, o fusionando K-bloque local si crece).
No he trabajado con ellos, pero también podría considerar particiones de espacio binarias . Estos le permiten usar árboles binarios en lugar de k-árboles para particionar su espacio. Entiendo que los KDTrees son un caso especial de esto.
Pero en cualquier caso, pensé que los algoritmos de inserción / eliminación para árboles de 2 ^ K y / o BSP / KDTrees se entendían bien y eran rápidos. Entonces, los cambios en el tamaño de la hiperesfera provocan operaciones de eliminación / inserción, pero son rápidos. Entonces no entiendo tu objeción a los árboles KD.
Creo que el rendimiento de todos estos son asintóticamente iguales.
Dado un espacio k-dimensional continuo (euclidiano) lleno de hiperesferas que se mueven / crecen / contraen de manera impredecible, necesito encontrar repetidamente la hiperesfera cuya superficie esté más cerca de una determinada coordenada. Si algunas hiperesferas están a la misma distancia de mi coordenada, entonces la mayor hiperesfera gana. (Se garantiza que la cuenta total de hiperesferas se mantendrá igual a lo largo del tiempo).
Lo primero que pensé fue usar un KDTree pero no tomará en cuenta los volúmenes no uniformes de las hiperesferas. Así que busqué más y encontré BVH (Jerarquías de Volumen Límite) y BIH (Jerarquías de Intervalo de Enlace), que parecen ser el truco. Al menos en el espacio de 2/3 dimensiones. Sin embargo, al encontrar bastante información y visualizaciones en los BVH, apenas pude encontrar nada en los BIH.
Mi requisito básico es una estructura de datos espaciales en k dimensiones que tenga en cuenta el volumen y que sea súper rápida de construir (fuera de línea) o dinámica con apenas desequilibrios .
Teniendo en cuenta mis requisitos anteriores, ¿con qué estructura de datos irías? ¿Algún otro que ni siquiera mencioné?
Edit 1: Olvidé mencionar: ¡los hypershperes están permitidos (en realidad muy esperados) para superponerse!
Editar 2: Parece que en lugar de "distancia" (y "distancia negativa" en particular) mi métrica descrita coincide mucho mejor con el poder de un punto .
Usaría la extensión R * Tree para SQLite. Una tabla normalmente tendría 1 o 2 datos dimensionales. Las consultas SQL pueden combinar varias tablas para buscar en dimensiones superiores.
La formulación con distancia negativa es un poco rara. La distancia es positiva en geometría, por lo que puede no haber mucha teoría útil para usar.
Una formulación diferente que use solo distancias positivas puede ser útil. Lea sobre espacios hiperbólicos. Esto podría ayudar a proporcionar ideas para otras formas de describir la distancia.