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

Question

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, "Encuéntrame los 3 restaurantes más cercanos a este punto en un mapa").

¿Puede alguien indicarme una discusión teórica de los algoritmos implicados? Quiero saber 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, anchura 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 poder hacer después consultas a los datos como "dada la cara de esta persona, encuéntrame las 100 caras más parecidas".

¿Existe actualmente algún programa informático que ofrezca la posibilidad de buscar en estos espacios generalizados?

Answer 1

La respuesta clásica (paleogeográfica) es utilizar un árbol K-D para almacenar los datos (véase http://en.wikipedia.org/wiki/Kd-tree ). Funcionan dividiendo los datos en dos particiones en cada dimensión a medida que se desciende en el árbol. La ventaja es que, al encontrar el elemento más cercano, también se puede crear una lista de elementos más cercanos sin coste adicional, de modo que responder a cuáles son los tres restaurantes más cercanos es tan fácil como encontrar el más cercano.

He leído en alguna parte que eHarmony utiliza árboles K-D para encontrar "parejas compatibles" en 14 dimensiones.

Answer 2

En los artículos de la revista "The New York Times" aparecen buenas descripciones de los algoritmos en 2 y 3 dimensiones. texto clásico de Preparata & Shamos . Los algoritmos utilizados en los SIG son una especialidad de Hanan Samet que ha publicado varios libros sobre el tema.

Las búsquedas de mayor dimensión suelen estar asistidas o aceleradas por medio de técnicas preliminares de extracción de datos, agrupación o reducción de dimensiones. Esto es más bien una cuestión de análisis de datos y estadística, no de SIG, que por su naturaleza se centra en búsquedas de una a cuatro dimensiones euclidianas. Para más información, busque en nuestro foro hermano stats.stackexchange.com para términos probables como agrupación , reducción de la dimensionalidad y escalamiento multidimensional y para las menos obvias como pca (análisis de componentes principales) y svm (máquinas de vectores de apoyo). También es un buen lugar para preguntar sobre el software existente.

Answer 3

He oído que Netezza ha puesto en marcha algunas innovaciones espacial algoritmos de procesamiento paralelo. El libro blanco es aquí .

La arquitectura de Procesamiento Paralelo Asimétrico Procesamiento Paralelo 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 a consultas complejas a gran escala de datos datos espaciales y no espaciales sin la complejidad, el ajuste y las agregaciones necesarias en los sistemas tradicionales.

Actualización

Olvidé mencionar que Netezza aprovecha en gran medida Teorema de Bayes . Aquí hay una colección de vídeos aquí .