Estoy interesado en buena literatura sobre índices espaciales. Cuáles están en uso, comparaciones entre ellos en cuanto a velocidad, requisitos de espacio, desempeño de consultas espaciales al usarlos, etc.Buenos libros/artículos sobre índices espaciales
Solía usar un tipo de QuadTree casero para la indexación espacial (mucho antes de aprender la palabra "quadtree "). Para los tipos ordinarios de datos espaciales (trato con los datos del mapa de calles), son rápidos de crear y rápidos de consultar, pero escanean demasiados nodos hoja durante las consultas. Específicamente, con tamaños de nodo razonables (50-100), mi quadtree tendió a producir alrededor de 300 resultados para una consulta puntual, es decir, se aplican 3-6 nodos de hoja (estadio muy difícil; los resultados son muy variables)
Hoy en día, mi la estructura de datos preferida es el árbol R *. Escribí y probé una implementación yo mismo que obtuvo muy buenos resultados. Mi código para construir un árbol R * es muy lento en comparación con mi código QuadTree, pero los cuadros delimitadores en los nodos hoja terminan muy bien organizados; al menos la mitad del espacio de consulta es respondida por un solo nodo hoja (es decir, si realiza una consulta de punto aleatorio, hay una buena probabilidad de que solo se devuelva un nodo hoja individual), y algo así como el 90% del espacio está cubierto por dos nodos o menos Entonces, con un tamaño de nodo de 80 elementos, típicamente obtengo 80 o 160 resultados de una consulta puntual, con un promedio más cercano a 160 (ya que algunas consultas devuelven 3-5 nodos). Esto es cierto incluso en áreas urbanas densas del mapa.
Lo sé porque escribí un visualizador para mi árbol R * y los objetos gráficos dentro de él, y lo probé en un gran conjunto de datos (600,000 segmentos de carretera). Funciona incluso mejor en datos puntuales (y otros datos en los que los cuadros delimitadores rara vez se superponen). Si implementa un árbol R *, le insto a que visualice los resultados, porque cuando escribí el mío tenía varios errores que disminuían la eficacia del árbol (sin afectar la corrección), y pude ajustar algunas de las decisiones a obtener mejores resultados Asegúrese de probar en un conjunto de datos grande, ya que revelará problemas que un pequeño conjunto de datos no puede. Puede ayudar a disminuir el despliegue (tamaño del nodo) del árbol para la prueba, para ver qué tan bien funciona el árbol cuando tiene varios niveles de profundidad.
Estaré encantado de darle el código fuente, excepto que necesitaría el permiso de mi empleador. Tú sabes cómo es. En mi implementación, apoyo la reinserción forzada, pero mi pena de inserción de PickSplit y ha sido modificada.
El papel original, The R* tree: An Efficient and Robust Access Method for Points and Rectangles, falta puntos por algún motivo (sin puntos y sin puntos en la "i" s). Además, su terminología es un poco extraña, p. cuando dicen "margen", lo que quieren decir es "perímetro".
El árbol R * es una buena opción si necesita una estructura de datos que se pueda modificar. Si no necesita modificar el árbol después de crearlo por primera vez, considere bulk loading algorithms. Si solo necesita modificar el árbol una pequeña cantidad después de la carga masiva, los algoritmos ordinarios de R-tree serán lo suficientemente buenos. Tenga en cuenta que los datos del árbol R * y del árbol R son estructuralmente idénticos; solo los algoritmos para inserción (y tal vez eliminación? me olvido) son diferentes. R-tree es la estructura de datos original de 1984; aquí hay un enlace al R-tree paper.
El kd-tree parece eficiente y no demasiado difícil de implementar, pero solo se puede usar para datos de puntos.
Por cierto, la razón me centro en los nodos hoja tanto es que
Desarrollé un algoritmo para la búsqueda rápida basada en cuadrantes y lo publiqué en ddj.com hace un par de años. Tal vez sea de su interés:
búsqueda acelerada para la línea más cercana http://drdobbs.com/windows/198900559