Existe-t-il un moyen d'utiliser un magasin de valeurs-clés pour les données géospatiales?

J'ai utilisé de nombreuses bases de données relationnelles dans le passé, mais j'ai également lu toutes les bases de données NoSQL et les magasins de valeurs-clés semblent intéressants.

Lorsque je stocke un objet géométrique, j'utilise principalement cinq colonnes indexées ID, MIN_X, MAX_X, MIN_Y et MAX_Y (où X et Y sont dans une projection cartographique). Je n'ai pas besoin d'un index sur mes autres données.

J'ai besoin des valeurs X et Y pour rechercher des objets dans un endroit spécifié (rectangle de carte), et j'ai besoin de la valeur ID si je veux mettre à jour un objet spécifié.

Existe-t-il un moyen d'utiliser un magasin de valeurs-clés pour cela?

Nous utilisons Google AppEngine pour exécuter des requêtes spatiales / d'attributs et le principal problème (dès le premier jour) est de savoir comment indexer de grands ensembles de lignes / polygones de taille arbitraire. Les données ponctuelles ne sont pas trop difficiles (voir geohash, geomodel, etc.) mais les ensembles de petits / grands polygones regroupés de manière aléatoire ont toujours été un problème (et dans certains cas, le sont toujours)

J'ai essayé plusieurs versions différentes de l'indexation spatiale sur GAE, mais la plupart ne sont que des variantes de deux ci-dessous. Aucun n'était aussi rapide que les bases de données SQL et tous ont des avantages / inconvénients. Cependant, les compromis semblent raisonnables pour la plupart des applications de cartographie basées sur Internet. En outre, les deux ci-dessous doivent être couplés à une élimination de la géométrie en mémoire (via JTS, etc.) pour supprimer toutes les fonctionnalités qui ne correspondent pas aux paramètres de recherche finaux. et enfin, ils s'appuient sur des fonctionnalités spécifiques à GAE mais je suis sûr qu'il pourrait être appliqué à d'autres architectures (ou utiliser TyphoonAE pour fonctionner sur un cluster Linux, ec2, etc.)

Grilles - Emballez toutes les fonctionnalités d'une certaine zone dans un index de grille connu. Placez un petit index spatial sur la grille afin de parcourir rapidement l'ensemble des entités qu'il contient. Pour la plupart des requêtes, vous n'aurez besoin que de tirer une poignée de grilles, ce qui est rapide, car vous connaissez la convention de dénomination exacte de la grille et sa relation avec les entités K / V (obtient, pas les requêtes)

Avantages - assez rapide, facile à mettre en œuvre, pas d'empreinte mémoire.

Inconvénients - un prétraitement est nécessaire, l'utilisateur doit décider de la taille de la grille, les grandes géométries sont partagées sur plusieurs grilles, le clustering peut entraîner une surcharge des grilles, les coûts de sérialisation / désérialisation peuvent être un problème (même lorsqu'ils sont compressés via des tampons de protocole)

QuadKeys - Il s'agit de l'implémentation actuelle. Fondamentalement, c'est la même chose que Grids, sauf qu'il n'y a pas de niveau de grille défini. au fur et à mesure que des fonctionnalités sont ajoutées, elles sont indexées par la grille à quatre clés qui contient complètement leurs limites (ou, dans certains cas, divisées en deux lorsqu'une seule quadruple clé ne peut pas être utilisée, pensez à la ligne de données). Une fois le qk trouvé, il est ensuite divisé en un nombre maximum de qk plus petits qui fournissent des représentations de grain plus fines de l'entité. un pointeur / bbox vers cette fonctionnalité est ensuite compressé dans un gridindex léger (groupe de fonctionnalités) qui peut être interrogé (une conception originale a interrogé directement les fonctionnalités mais cela s'est avéré trop lent / intensif en CPU dans les cas où l'ensemble de résultats était grand)

Quadline de polyligne http://www.arc2earth.com/images/help/GAE_QKS_1.png Quadkeys de polygone http://www.arc2earth.com/images/help/GAE_QKS_2.png

La convention de dénomination quadruple utilisée ci-dessus est bien connue et, plus important encore, tend à préserver la localité (décrite plus ici )

Le polygone ci-dessus ressemble à ceci: 0320101013123 03201010131212 03201010131213 0320101013132 0320101013133 03201010131302 032010101313303 032010101313002 032010101313003 032010101313012 032010101313013 032010101313101313131313131313131313101013131013131010

si les limites de la requête sont suffisamment petites, vous pouvez directement récupérer via le qk. ceci est optimal car il ne s'agit que d'un seul appel rpc par lots à la banque de données GAE. si les limites sont suffisamment grandes pour inclure trop de qks possibles (> 1000), vous pouvez également interroger en utilisant un filtre (ex: qk> = 0320101013 et qk <= 0320101013 + \ ufffd). La convention de dénomination à quatre clés ainsi que la façon dont GAE indexe les chaînes permet à la requête ci-dessus d'extraire uniquement les grilles existantes qui sont inférieures à cette valeur qk.

il y a d'autres mises en garde et problèmes de perf mais en général, sa capacité à interroger sur les quadkeys qui le rend possible

exemples - requête sur les comtés américains: geojson

Avantages - assez rapide, pas de configuration de taille de grille, pas d'empreinte mémoire, pas de grilles surchargées

Inconvénients - prétraitement nécessaire, sur-extraction possible dans certains scénarios, pas de données polaires

Courbes de remplissage d'espace - Jetez un coup d'œil à la présentation des requêtes NextGen d'Alfred à Google I / O cette année. L'inclusion de courbes génériques de remplissage espace / temps ainsi que les nouveaux opérateurs MultiQuery (exécutés en parallèle) permettront des requêtes spatiales vraiment cool. Va-t-il battre les performances SQL traditionnelles? Difficile à dire mais ça devrait très bien évoluer. Et nous approchons rapidement d'un avenir où des appareils mobiles toujours connectés de toutes formes / tailles augmenteront considérablement le trafic vers votre site / service.

enfin, je conviens également que vous devriez examiner de très près votre domaine problématique avant de choisir NoSQL plutôt que SQL. Dans notre cas, j'ai vraiment aimé le modèle de tarification de GAE, donc il n'y avait vraiment pas de choix mais si vous n'avez pas besoin de faire évoluer, gagnez du temps et utilisez simplement un db sql standard

J'ai entendu parler de GeoCouch, qui est une implémentation de CouchDB pour les données basées sur la localisation. Et je pense aussi que MongoDB a des capacités d'indexation géospatiale.

Il s'agit principalement d'une question sur les algorithmes. Stack Overflow peut également être un bon endroit pour le demander.

Dans tous les cas, la réponse à votre question directe est "oui, vous pouvez utiliser un magasin kvp pour représenter les données spatiales". Une meilleure question, cependant, pourrait être "DEVRAIS-JE utiliser un magasin kvp pour représenter des données spatiales?"

La réponse à cette question (comme beaucoup d'autres) est "ça dépend". Cela dépend de votre échelle, de votre charge de travail (transactionnelle), de la nature des données et de l'infrastructure informatique dont vous disposez.

Un magasin kvp aura une faible surcharge, ce qui peut aider à augmenter le débit pour des volumes élevés d'insertion et de mise à jour du parallélisme. Il ne sera cependant pas très rapide d'effectuer des recherches spatiales (trouver tous les objets dans un rectangle). Pour cela, vous voudriez un index spatial, comme un R-Tree.

Cependant, si vous avez un très grand volume de données et un énorme cluster d'ordinateurs, l'utilisation d'un index kvp pourrait offrir certains avantages de perormance. La seule façon de savoir avec certitude est de prendre des mesures de performances en utilisant les données réelles et d'accéder aux pattens que vous vous attendez à rencontrer.

Mise à jour :

Voici un peu plus d'informations. Vous pouvez utiliser un magasin KVP pour effectuer des recherches spatiales. Le problème est que c'est lent. Pour voir pourquoi, considérez quelque chose comme ceci:

  ***********
  ***********
  ***********
  ***********
  ****###****
  ****###****
  ****###****
  ***********
  ***********
  ***********
  ***********

Où * et # représentent des objets, disposés dans une grille 11x11, avec l'origine dans le coin supérieur gauche. Imaginez une recherche d'objets dans le rectangle (4,4) - (7,7). Cela devrait trouver tous les "#". En supposant que vous utilisez un arbre b + pour représenter vos index dans le magasin KVP, vous pouvez trouver les résultats à l'aide de l'index "X" ou de l'index "Y". Dans ce cas, peu importe lequel. Pour les besoins de la discussion, je vais utiliser l'index x. Vous feriez une recherche log (n) dans l'index X pour trouver le premier nœud avec une valeur X de "4", puis parcourez les nœuds foliaires b + jusqu'à ce que vous trouviez un nœud avec une valeur supérieure à 7. Comme vous parcourez l'index x, vous rejetteriez alors tout ce qui était en dehors de la plage y souhaitée.

C'est lent. Imaginez-le sur une grande grille, avec la même densité, disons 100 K * 100 K. Là, vous auriez à scanner "300, 000" entrées d'index pour ne trouver que 9 enregistrements. Si vous utilisez un arbre R correctement équilibré, cependant, la recherche d'index n'aura probablement besoin que d'analyser environ 90 enregistrements. Voilà une énorme différence.

Le problème, cependant, est que le maintien d'un arbre R équilibré coûte cher. C'est pourquoi la réponse est "cela dépend" et pourquoi la question "devrais-je faire cela" est beaucoup plus importante que "comment dois-je faire".

Si vous insérez et supprimez beaucoup d'enregistrements, et que vous effectuez principalement la recherche "ID d'objet" et que vous ne faites pas fréquemment la recherche "spatiale", l'utilisation de votre index KVP vous donnera de meilleures performances pour ce que vous voulez réellement utiliser le système pour . Cependant, si vous insérez ou supprimez rarement, mais que vous effectuez souvent des recherches spatiales, vous devez utiliser un R-Tree.

Si vous utilisez des valeurs lat / long, vous pourrez peut-être utiliser des géohashes comme partie de la valeur de votre magasin.

En voici un pour NYC. dr5regy6rc6ye

Avec le geohash, vous pouvez commencer à supprimer les caractères à la fin du geohash pour obtenir une grille de précision variable: http://geohash.org/dr5re

Exemple d'implémentation js: http://github.com/davetroy/geohash-js

Dans la majorité des cas, vous obtiendrez plus d'utilité du stockage de données relationnelles que du stockage de clé / valeur ou clé / valeur / type. Il existe des complexités considérables autour de l'interrogation et de la génération de rapports efficaces sur ce type de schéma de données.

Mon conseil serait d'évaluer attentivement si votre balance nécessite réellement NoSQL avant d'envisager comment l'utiliser.

Jetez un œil à cette application GAE qui sérialise la géométrie JTS vers BigTable . Vous pourrez peut-être l'adopter pour d'autres moteurs de stockage NoSQL .

MongoDB a la possibilité de créer et de consommer des index géospatiaux basés sur des propriétés de tuple 2d [x, y] strictes de Documents, et autorise les requêtes de type "proche" et "limite". Cependant, il ne gère aucune correction pour les projections et utilise un modèle idéalisé d'une terre plate

J'utiliserais les magasins de clés / valeurs uniquement comme couche de mise en cache, voir http://www.membase.org/ ou http://wiki.basho.com/display/RIAK/How+Things+Work (riak_kv_cache_backend)

Selon les besoins de votre application, vous souhaiterez peut-être toujours avoir un accès SQL aux données.

Il s'agit certainement d'un domaine d'intérêt émergent, quelques discussions à venir de la conférence FOSS4G :

• GeoCouch: un index spatial pour CouchDB
• Indexation géospatiale avec MongoDB
• Au-delà de PostGIS
• Indexation spatiale distribuée dans le cloud