¿Comprender el almacenamiento de ubicación y los algoritmos de consulta?

Uno de los aspectos más importantes de una base de datos equipada con SIG es que proporciona al usuario la capacidad de consultar rápidamente todos los puntos dentro de un área geográfica arbitraria que coincidan con algunos criterios adicionales. (Por ejemplo, "Búscame los 3 restaurantes más cercanos a este punto en un mapa").

¿Alguien puede señalarme una discusión teórica de los algoritmos involucrados? Quiero aprender cómo funcionan.

En última instancia, quiero aplicar la misma capacidad a conjuntos generalizados de datos numéricos: una gran nube de puntos en un espacio arbitrario, n-dimensional y no euclidiano. Por ejemplo, la cara de una persona puede caracterizarse como un vector de números: [distancia entre los ojos, distancia del ojo a la boca, ancho de la cara, longitud de la cara, etc.]. Quiero filmar el tráfico de la acera, estimar las características de la cara de cada persona y luego poder hacer consultas a los datos más adelante, como "dada la cara de esta persona, encuéntrame las 100 caras más similares".

¿Existe actualmente algún software existente que brinde la capacidad de buscar en estos espacios generalizados?

En el texto clásico de Preparata & Shamos aparecen buenas cuentas de algoritmos en 2 y 3 dimensiones . Los algoritmos utilizados en los SIG son una especialidad de Hanan Samet , quien ha publicado varios libros sobre el tema.

Las búsquedas de dimensiones superiores generalmente son asistidas o aceleradas por medio de minería de datos preliminar, agrupamiento o técnicas de reducción de dimensiones. Esto es más una cuestión de análisis de datos y estadísticas, no de SIG, que por su naturaleza se centra en búsquedas en una a cuatro dimensiones euclidianas. Para obtener más información, busque en nuestro foro hermano stats.stackexchange.com los términos probables, como agrupamiento , reducción de dimensionalidad y escalamiento multidimensional, y otros menos obvios como pca (análisis de componentes principales) y svm (máquinas de vectores de soporte). Ese también es un buen lugar para preguntar sobre el software existente.

La respuesta clásica (paleogeógrafo) es usar un árbol KD para almacenar los datos (ver http://en.wikipedia.org/wiki/Kd-tree ). Funcionan dividiendo aproximadamente los datos en dos particiones en cada dimensión a medida que avanza hacia abajo en el árbol. La ventaja de ellos es que a medida que encuentra el artículo más cercano, también puede crear una lista de los artículos más cercanos a medida que avanza sin costo adicional, por lo que responder cuáles son los tres restaurantes más cercanos es tan fácil como encontrar el más cercano.

Leí en alguna parte que eHarmony usa árboles KD para encontrar "coincidencias compatibles" en 14 dimensiones.

He oído que Netezza ha implementado algunos innovadores algoritmos de procesamiento espacial paralelo. El libro blanco está aquí .

La arquitectura de procesamiento paralelo masivo asimétrico de Netezza proporciona la mejor combinación de multiprocesamiento simétrico (SMP) y procesamiento paralelo masivo (MPP), facilitando el procesamiento de consultas complejas en terascala de datos espaciales y no espaciales sin la complejidad, ajuste y agregaciones necesarias en los sistemas tradicionales.

Actualizar

Olvidé mencionar que Netezza aprovecha en gran medida el teorema de Bayes . Aquí hay una colección de videos aquí .