Existe alguma maneira de usar um armazenamento de valor-chave para dados geoespaciais?

26

Eu usei muitos bancos de dados relacionais no passado, mas também li sobre todos os bancos de dados NoSQL, e os armazenamentos Key-Value parecem interessantes.

Quando armazeno objetos geométricos, uso principalmente cinco IDs de colunas indexadas, MIN_X, MAX_X, MIN_Y e MAX_Y (onde X e Y estão em uma projeção de mapa). Não preciso de um índice nos meus outros dados.

Preciso dos valores X e Y para pesquisar objetos em um local especificado (retângulo do mapa) e preciso do valor do ID se desejar atualizar um objeto especificado.

Existe alguma maneira de usar um armazenamento de valor-chave para isso?

Jonas
fonte

Respostas:

18

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.

bFlood
fonte
Você mencionou o GAE, mas qual banco de dados você está usando? Existem vários: cloud.google.com/products/storage
Don McCurdy
11

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.

JoshFinnie
fonte
Sim, ambos o fazem, e o SimpleGeo está construindo uma extensão espacial para Cassandra. Não ouvi nada no Voldemort ou no MemCache
TheSteve0:
Ah, eu amo o que a SimpleGeo está fazendo. Estou com ciúmes e adoraria trabalhar para eles!
21710 JoshFinnie
8

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.

Scott Wisniewski
fonte
Eu não aceitaria uma resposta como "sim, você pode". porque eu quero saber como . E "DEVO EU .." não é uma pergunta melhor, porque, como você disse, "depende".
Jonas
11
Eu tenho que discordar de você. Se você deseja construir um sistema útil ou deixar uma referência útil na Internet para outras pessoas que construam sistemas similares, "eu devo" é muito mais importante do que "como". No interesse de ser útil, no entanto, editei minha resposta para fornecer algumas informações sobre como.
22410 Scott Scottnniewski
@ Jonas: Eu acredito que as respostas que você recebeu foram por causa da maneira como você fez a pergunta: "mas eu também li sobre todos os bancos de dados NoSQL, e as lojas Key-Value parecem interessantes". Isso tem todas as características de uma solução que procura um problema.
27410 JasonBirch
O NoSQL resolve um problema, mas é praticamente um problema porque ninguém está trabalhando em uma escala suficientemente grande. Infelizmente, é sempre bom pensar que nossos próprios sistemas são maiores no grande esquema das coisas do que realmente são. :)
JamesRyan
1

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.

JasonBirch
fonte
11
Aqui está um exemplo de um problema que você pode ter (e uma solução para ele) se precisar calcular se um ponto está dentro ou fora de uma geometria. code.google.com/p/giscloud/wiki/SerializedSpatialIndexes
Jon Bringhurst
Hey @ Jon, isso seria melhor adicionado como resposta. Dessa forma, ele pode se sustentar por si próprio, e você receberá crédito se as pessoas acharem que ele tem mérito!
JasonBirch