Comprendre les algorithmes de stockage d'emplacement et de requête?

L'un des aspects les plus importants d'une base de données équipée d'un SIG est qu'elle permet à l'utilisateur de rechercher rapidement tous les points d'une zone géographique arbitraire qui correspondent à certains critères supplémentaires. (Par exemple, "Trouvez-moi les 3 restaurants les plus proches de ce point sur une carte.")

Quelqu'un peut-il m'indiquer une discussion théorique des algorithmes impliqués? Je veux savoir comment ils fonctionnent.

En fin de compte, je veux appliquer la même capacité à des ensembles généralisés de données numériques - un grand nuage de points dans un espace arbitraire, à n dimensions, non euclidien. Par exemple, le visage d'une personne peut être caractérisé comme un vecteur de nombres: [distance entre les yeux, distance entre les yeux et la bouche, largeur du visage, longueur du visage, etc.]. Je veux filmer le trafic sur les trottoirs, estimer les caractéristiques du visage de chaque personne, puis être en mesure d'interroger les données plus tard, telles que "étant donné le visage de cette personne, trouvez-moi les 100 visages les plus similaires".

Existe-t-il actuellement un logiciel existant qui permet de rechercher dans ces espaces généralisés?

De bons comptes d'algorithmes en 2 et 3 dimensions apparaissent dans le texte classique de Preparata & Shamos . Les algorithmes utilisés dans les SIG sont une spécialité de Hanan Samet , qui a publié plusieurs livres sur le sujet.

Les recherches de dimension supérieure sont généralement assistées ou accélérées au moyen de techniques préliminaires d'exploration de données, de regroupement ou de réduction de dimension. Il s'agit plus d'une analyse de données et de statistiques que d'un SIG qui, par nature, se concentre sur des recherches dans une à quatre dimensions euclidiennes. Pour plus d'informations, recherchez sur notre forum partenaire stats.stackexchange.com des termes probables tels que clustering , réduction de dimensionnalité et mise à l'échelle multidimensionnelle et des termes moins évidents comme pca (analyse des composants principaux) et svm (machines à vecteurs de support). C'est également un bon endroit pour poser des questions sur les logiciels existants.

La réponse classique (paléogéographe) consiste à utiliser un arbre KD pour stocker les données (voir http://en.wikipedia.org/wiki/Kd-tree ). Ceux-ci fonctionnent en divisant à peu près les données en deux partitions dans chaque dimension tour à tour lorsque vous descendez dans l'arborescence. Leur avantage est que lorsque vous trouvez l'article le plus proche, vous pouvez également créer une liste des articles les plus proches au fur et à mesure sans frais supplémentaires, il est donc aussi facile de répondre aux trois restaurants les plus proches que de trouver le plus proche.

J'ai lu quelque part qu'eHarmony utilise des arbres KD pour trouver des "correspondances compatibles" en 14 dimensions.

J'ai entendu dire que Netezza a implémenté des algorithmes innovants de traitement parallèle spatial . Le livre blanc est ici .

L'architecture de traitement massivement parallèle asymétrique de Netezza offre la meilleure combinaison de multitraitement symétrique (SMP) et de traitement massivement parallèle (MPP), facilitant le traitement terascale et complexe des requêtes de données spatiales et non spatiales sans la complexité, le réglage et les agrégations nécessaires dans les systèmes traditionnels.

Mise à jour

J'ai oublié de mentionner que Netezza s'appuie fortement sur le théorème de Bayes . Voici une collection de vidéos ici .