Usamos o Google AppEngine para executar consultas espaciais / de atributo e o principal problema (desde o primeiro dia) é como indexar grandes conjuntos de linhas / polígonos de tamanho arbitrário. Os dados pontuais não são muito difíceis (consulte geohash, geomodel etc.), mas conjuntos de polígonos pequenos / grandes agrupados aleatoriamente sempre foram um problema (e, em alguns casos, ainda são)
Eu tentei várias versões diferentes de indexação espacial no GAE, mas a maioria são apenas variantes de duas abaixo. Nenhum foi tão rápido quanto os bancos de dados SQL e todos têm vantagens / desvantagens. as compensações parecem razoáveis para a maioria dos aplicativos de mapeamento na Internet. Além disso, os dois abaixo precisam ser acoplados ao descarte de geometria na memória (via JTS etc.) para remover todos os recursos que não se encaixam nos parâmetros finais de pesquisa. e, finalmente, eles contam com recursos específicos do GAE, mas tenho certeza de que podem ser aplicados a outras arquiteturas (ou usar o TyphoonAE para executar em um cluster linux, ec2 etc.)
Grades - Empacote todos os recursos de uma determinada área em um índice de grade conhecido. Coloque um pequeno índice espacial na grade para navegar rapidamente pelo conjunto de recursos que ela contém. Para a maioria das consultas, você só precisará puxar um punhado de grades, o que é rápido, pois você conhece a convenção de nomenclatura exata da grade e como ela está relacionada às entidades K / V (recebe, não consultas)
Prós - muito rápido, fácil de implementar, sem pegada de memória.
Contras - é necessário pré-processamento, o usuário precisa decidir o tamanho da grade, os geoms grandes são compartilhados em várias grades, o cluster pode causar sobrecarga nas grades, os custos de serialização / desserialização podem ser um problema (mesmo quando compactados por buffers de protocolo)
QuadKeys - Esta é a implementação atual. basicamente é o mesmo que grades, exceto que não há um nível de grade definido. À medida que os recursos são adicionados, eles são indexados pela grade quadkey que contém completamente seus limites (ou, em alguns casos, divididos em dois quando uma única quadkey não pode ser usada, pense na linha de dados). Depois que o qk é encontrado, ele é dividido em um número máximo de qk menor que fornece representações mais finas do recurso. um ponteiro / bbox para esse recurso é compactado em um índice de grade leve (grupo de recursos) que pode ser consultado (um design original consultou os recursos diretamente, mas isso se mostrou muito lento / com muita CPU nos casos em que o conjunto de resultados era grande)
Polykey
Quadkeys http://www.arc2earth.com/images/help/GAE_QKS_1.png Polykey Quadkeys http://www.arc2earth.com/images/help/GAE_QKS_2.png
A convenção de nomenclatura quadkey usada acima é bem conhecida e, mais importante, tende a preservar a localidade (descrita mais aqui )
O polígono acima se parece com isso: 0320101013123 03201010131212 03201010131213 0320101013132 0320101013133 03201010131302 03201010131303 032010101313002 032010101313003 032010101313012 032010101313013 03201010131313 0320101013103
se os limites da consulta forem pequenos o suficiente, você poderá buscar diretamente por meio do qk. isso é ideal, pois é apenas uma única chamada em lote rpc para o armazenamento de dados GAE. se os limites forem grandes o suficiente para incluir muitos qks possíveis (> 1000), você poderá alternativamente consultar usando um filtro (ex: qk> = 0320101013 e qk <= 0320101013 + \ ufffd). A convenção de nomenclatura quadkey mais a maneira como o GAE indexa as strings permite que a consulta acima busque apenas as grades existentes que ficam abaixo desse valor qk.
existem outras advertências e problemas de desempenho, mas, em geral, é a capacidade de consultar as quadkeys que o torna viável
exemplos - consultas em municípios dos EUA: geojson
Prós - bem rápido, sem configuração de tamanho de grade, sem espaço de memória, sem superlotação
Contras - pré-processamento necessário, possível busca excessiva em alguns cenários, sem dados polares
Curvas de preenchimento de espaço - Dê uma olhada nas consultas NextGen de Alfred no Google I / O este ano. A inclusão de curvas genéricas de preenchimento de espaço / tempo juntamente com os novos operadores MultiQuery (executados em paralelo) permitirá algumas consultas espaciais realmente interessantes. Será que vai superar o desempenho tradicional do SQL? Difícil dizer, mas deve escalar muito bem. E estamos nos aproximando rapidamente de um futuro em que dispositivos móveis sempre ativados, de todas as formas / tamanhos, aumentarão drasticamente o tráfego do seu site / serviço.
por fim, eu também concordo que você deve examinar com muita atenção o domínio do problema antes de escolher o NoSQL sobre SQL. No nosso caso, gostei muito do modelo de preços do GAE; portanto, não havia escolha, mas se você não precisar escalar, economize um pouco de tempo e use apenas um banco de dados sql padrão.
Eu ouvi falar do GeoCouch, que é uma implementação do CouchDB para dados baseados em localização. E também acho que o MongoDB possui recursos de indexação geoespacial.
fonte
Esta é principalmente uma pergunta sobre algoritmos. O estouro de pilha também pode ser um bom lugar para perguntar.
De qualquer forma, a resposta para sua pergunta direta é "sim, você pode usar um armazenamento kvp para representar dados espaciais". Uma pergunta melhor, no entanto, pode ser "DEVO usar um armazenamento kvp para representar dados espaciais?"
A resposta para essa pergunta (como muitas outras) é "depende". Depende da sua escala, da sua carga de trabalho (transacional), da natureza dos dados e da infraestrutura computacional que você tem à sua disposição.
Um armazenamento kvp terá uma sobrecarga baixa, o que pode ajudar a aumentar a taxa de transferência para altos volumes de inserção e atualizar o paralelismo. No entanto, não será muito rápido a realização de pesquisas espaciais (encontre todos os objetos em um retângulo). Para isso, você deseja um índice espacial, como um R-Tree.
No entanto, se você tiver um volume de dados realmente grande e um enorme cluster de computadores, o uso de um índice kvp poderá fornecer alguns benefícios de desempenho. A única maneira de realmente ter certeza é fazer medições de desempenho usando os dados reais e acessar os padrões que você espera encontrar.
Atualização :
Aqui está um pouco mais de informação. Você pode usar uma loja KVP para fazer pesquisas espaciais. O problema é que é lento. Para ver o porquê, considere algo como isto:
Onde * e # representam objetos, dispostos em uma grade 11x11, com a origem no canto superior esquerdo. Imagine uma busca por objetos dentro do retângulo (4,4) - (7,7). Isso deve encontrar todos os "#" 's. Supondo que você esteja usando uma árvore b + para representar seus índices no repositório KVP, você poderá encontrar os resultados usando o índice "X" ou o índice "Y". Nesse caso, não importa qual. Para fins de discussão, usarei o índice x. Você faria uma pesquisa de log (n) no índice X para encontrar o primeiro nó com um valor X de "4" e, em seguida, iteraria pelos nós de folha b + -tree até encontrar um nó com um valor maior que 7. Como você iterar pelo índice x, você rejeitaria qualquer coisa que estivesse fora do intervalo y desejado.
Isso é lento. Imagine-o em uma grade grande, com a mesma densidade, digamos 100 K * 100 K. Lá, você acabaria escaneando "300.000" entradas do índice para encontrar apenas 9 registros. Se você usar uma R-Tree adequadamente equilibrada, no entanto, a pesquisa de índice provavelmente precisará apenas verificar cerca de 90 registros. Essa é uma enorme diferença.
O problema, no entanto, é que manter um R-Tree equilibrado é caro. É por isso que a resposta é "depende" e por que a pergunta "devo fazer isso" é muito mais importante do que "como faço".
Se você inserir e remover muitos registros e fizer a pesquisa "ID do objeto" e não fizer a pesquisa "espacial" com frequência, o uso do índice KVP fornecerá um melhor desempenho para o que você realmente deseja usar o sistema. . No entanto, se você inserir ou excluir com pouca frequência, mas fizer muitas pesquisas espaciais, desejará usar uma R-Tree.
fonte
Se você estiver usando valores de lat / long, poderá usar geohashes como parte do valor da sua loja.
Aqui está um para NYC. dr5regy6rc6ye
Com a geohash, você pode começar a eliminar os caracteres no final da geohash para obter uma grade de precisão variável: http://geohash.org/dr5re
Exemplo de implementação js: http://github.com/davetroy/geohash-js
fonte
Na maioria dos casos, você obterá mais utilidade do armazenamento de dados relacionais do que do armazenamento de chave / valor ou chave / valor / tipo. Existem complexidades consideráveis em torno de consultas e relatórios eficientes sobre esse tipo de esquema de dados.
Meu conselho seria avaliar de perto se sua escala realmente requer NoSQL antes de considerar como usá-la.
fonte
Dê uma olhada neste aplicativo GAE que serializa a geometria JTS para BigTable . Você pode adotá-lo para outros mecanismos de armazenamento NoSQL .
fonte
O MongoDB tem a facilidade de criar e consumir índices geoespaciais com base em propriedades estritas de tupla 2d [x, y] de Documents, e permite consultas do tipo 'near' e 'bounds'. No entanto, ele não lida com correções de projeções e usa um modelo idealizado de terra plana
fonte
Eu usaria armazenamentos de chave / valor apenas como uma camada de cache, consulte http://www.membase.org/ ou http://wiki.basho.com/display/RIAK/How+Things+Work (riak_kv_cache_backend)
Dependendo das necessidades do seu aplicativo, você ainda pode querer ter acesso SQL aos dados.
fonte
Esta é certamente uma área de interesse emergente, algumas próximas palestras da conferência FOSS4G :
fonte