Pesquisa ciente de local com Apache Lucene e Solr

Combinam texto não estruturado e dados espaciais para aperfeiçoar seus aplicativos de pesquisa

Seja buscando a cafeteria mais próxima em um smartphone com GPS, próximo dos amigos via site de rede de relacionamento, ou todos os caminhões dentro da cidade que entregam um determinado produto, mais e mais pessoas e negócios estão usando serviços de pesquisa ciente de local. Criar tais serviços tem sido, com frequência, o domínio de soluções proprietárias e peritos geoespaciais caros. Recentemente, contudo, a biblioteca de pesquisa de código aberto, Apache Lucene, e o poderoso servidor de pesquisa ativado pelo Lucene, Apache Solr, adicionaram capacidades espaciais. O desenvolvedor do Lucene e Solr, Grant Ingersoll, leva você através do básico da pesquisa espacial e mostra como alavancar suas capacidades para ativar o seu próximo aplicativo ciente de local.

Grant Ingersoll, Member, Technical Staff, Lucid Imagination

Grant IngersollGrant Ingersoll é um fundador e membro da equipe técnica da Lucid Imagination. A participação de programação de Grant inclui recuperação de informações, aprendizagem por máquina, categorização textual, e extração. Grant é o co-fundador do projeto de aprendizagem por máquina do Apache Mahout, bem como um comprometido e contribuidor nos projetos Apache Lucene e Apache Solr. Ele também é o co-autor do Taming Text (Manning, disponível) que aborda ferramentas de fonte aberta para processamento de linguagem natural.



04/Mar/2010

Local, local, local! Assim como o local é essencial em imóveis, a pesquisa mais o conhecimento do local pode render dividendos significativos ao ajudar os usuários a encontrar informações de forma efetiva e eficiente. Por exemplo, se você for um provedor de diretório de negócios (tal como o site "Páginas Amarelas"), quando um usuário pesquisa um encanador, o site deve retornar resultados para encanadores próximos à casa do usuário. Se você operar um site de turismo, você pode querer que os viajantes possam pesquisar locais de interesse próximos ao seu destino, para localizar serviços que os ajudarão a desfrutar de sua visita. Se você estiver construindo um site de relacionamento social, você pode usar informações de local para ajudar os usuários a se conectarem com amigos. E a ubiquidade de dispositivos cientes de local, tais como sistemas de navegação em automóveis e câmeras ativadas com GPS— e o grande volume de dados de mapas publicamente disponíveis — fornecem uma ampla variedade de oportunidades para construir Sistemas de Informações Geográficas (GIS) que incorporam pesquisa para produzir resultados superiores para usuários finais.

O uso de informações espaciais vai bem além da pesquisa, porém neste artigo ficarei concentrado em como obter vantagem de informações espaciais para aperfeiçoar seu aplicativo de pesquisa, aproveitando as capacidades do Apache Lucene e Apache Solr. Por que usar um mecanismo de busca? De nenhuma forma constitui um requisito, considerando que estão disponíveis muitas ferramentas GIS boas (mesmo grátis). Entretanto, basear seu aplicativo em pesquisa oferece diversos recursos eficientes nos quais muitas outras abordagens tradicionalmente falham. Os sistemas de pesquisa são eficazes na combinação de dados estruturados e não estruturados, permitindo que os usuários insiram consultas de formulário-livre que pesquisem texto livre tais como descrições e títulos enquanto restringem ou alteram os resultados com base em dados geográficos. Por exemplo, um site de viagens poderia implementar um recurso através do qual um usuário possa encontrar todos os hotéis em Boston, Mass., com uma classificação de 4 estrelas e a frase cama confortável no texto de apresentação e serviço de quarto 24h na descrição — todos com resposta secundária. Um sistema de pesquisa, tal como Apache Solr também pode fornecer facetamento (consulte Recursos para informações sobre Solr e facetas), destaque, e verificação ortográfica no conjunto de resultado, de modo que o aplicativo possa ajudar os usuários a encontrar o que estão buscando de forma mais eficaz.

Iniciarei com uma breve revisão de alguns conceitos principais do Lucene, deixando os detalhes mais profundos para o leitor pesquisar. A seguir, abordarei alguns dos conceitos básicos de pesquisa geoespacial. GIS é um campo amplo que poderia facilmente consumir todo este artigo e muito mais, portanto, em vez disso, ficarei concentrado em alguns conceitos básicos que devem ser razoavelmente intuitivos, dada a necessidade de localizar serviços, pessoas e outros itens de interesse diariamente. Complementarei o artigo com alguma discussão das abordagens disponíveis para indexar e pesquisar informações espaciais usando o Lucene e o Solr. Basearei esses conceitos em um exemplo real, embora simples, usando dados do projeto OpenStreetMap (OSM) (consulte Recursos).

Recordando os principais conceitos Lucene

O Apache Lucene é uma biblioteca de pesquisa de alto desempenho baseada em Java™. O Apache Solr é um servidor de pesquisa que usa o Lucene para fornecer pesquisa, facetamento e muito mais capacidades em HTTP. Ambos estão licenciados sob a Licença de Software Apache comercial. Consulte Recursos para maiores informações sobre os recursos e APIs que cada um oferece.

No fundo, Solr e Lucene ambos representam conteúdo como um documento. Um documento é então feito de um ou mais campos mais um valor de reforço opcional indicando a importância do documento. Um campo é feito do conteúdo real a ser indexado ou armazenado mais metadados, informando ao Lucene como tratar esse conteúdo e um valor de reforço indicando a importância desse campo. Fica a seu critério decidir como representar seu conteúdo como documentos e campos, dependendo de como você queira pesquisar e de outro modo acessar as informações no documento. É possível ter um relacionamento de um-para-um entre uma única unidade de seu conteúdo ou um relacionamento de um-para-vários. Por exemplo, posso escolher representar uma única página Web como um documento com diversos campos, tais como títulos, palavras-chave e texto. Ou, no caso de um livro, posso escolher representar cada página do livro como um documento separado. Como será possível ver posteriormente, esta distinção é importante quando se destina a codificar dados espaciais para pesquisa. O conteúdo em um campo pode ser indexado ou apenas armazenado no estado para uso por um aplicativo. Se o conteúdo for indexado, então o aplicativo pode pesquisá-lo. O conteúdo indexado também pode ser analisado para produzir termos, frequentemente chamado de tokens. Um termo é a base para busca e uso no processo de pesquisa. Um termo é, com frequência, uma palavra, mas não precisa ser. Incentivo a exploração dos Recursos para saber mais sobre todos esses conceitos.

No parte de consulta, o Lucene e Solr oferecem ricas capacidades para expressar consultas de usuário, variando desde consultas de palavras-chave (termo) básicas até consultas de frase e caracteres curingas. Tanto o Lucene quanto o Solr também oferecem a habilidade de restringir o espaço que está sendo pesquisado através da aplicação de um ou mais filtros, que são essenciais para pesquisa espacial. Consultas de faixa e filtros de faixa estão entre os mecanismos essenciais para restringir o espaço. Em uma consulta de faixa (ou filtro), o usuário indica a necessidade de restringir todos os documentos pesquisados a estarem localizados entre dois valores que tenham uma classificação natural. Por exemplo, é comum usar uma consulta de faixa para localizar todos os documentos que ocorreram no último ano ou último mês. Por trás, o Lucene deve enumerar os termos nos documentos para identificar documentos que estejam enquadrados dentro da faixa. Como mostrarei posteriormente, ajustar isso é uma das chaves para o desempenho para filtragem em aplicativos de pesquisa espacial.

Lucene e Solr também fornecem a noção de consultas de função, que permite o uso do valor de um campo, tais como latitude e longitude, como parte do mecanismo de pontuação, em vez de simplesmente as estatísticas de coleta interna que compreendem o mecanismo de pontuação primária. Isto também entrará no jogo posteriormente no artigo, quando demonstrarei o uso de algumas funções baseadas em distância do Solr.


Conceitos de pesquisa geoespaciais

Primeiramente, ao construir um aplicativo de pesquisa espacial, é necessário identificar os dados espaciais a serem incluídos no aplicativo. Estes dados, com frequência, estão na forma de algum sistema geocodificado, tais como latitude, longitude e elevação, ou como um código Postal ou um endereço de rua específico. Quando mais formalizado for o sistema de codificação, mais fácil será trabalhar dentro de seu sistema. Por exemplo, a antiga canção "Over the River and Through the Woods" (você conhece a letra: "to Grandmother's house we go") codifica uma considerável quantidade de informações espaciais na letra da música (consulte Recursos). Mas nem tudo isso é útil em um sistema GIS, pois não temos ideia de onde ficam a floresta ou o rio. Contraste isso com as instruções detalhadas até a casa da Vovó que incluem um endereço inicial e um endereço final, e você perceberá por que os dados adequadamente codificados são importantes. (De modo interessante, os sistemas que conseguem extrair e codificar instruções e entidades geográficas mais genéricas — por exemplo, over the river ou near the brown house— e os seus motivos também podem ser bem úteis, porém essa discussão está além do escopo deste artigo.)

Indo além dos dados brutos, geocodificados usados para identificar locais, muitos sistemas GIS podem adicionar informações que ocorrem em relação aos locais físicos. Por exemplo, um sistema de navegação pode usar uma série de locais dispostos em ordem em um mapa para criar uma rota de viagem do ponto A até o ponto B. Ou um meteorologista pode sobrepor dados de chuva ou tempestade em um mapa de uma área e permitir que as pessoas pesquisem quantidades de chuva por local de interesse. Pessoas que vivem próximas umas das outras frequentemente agrupam áreas para formar códigos Postais, códigos de área, ou mesmo vilas, cidades e estados. No caso de OSM, os usuários podem editar e sobrepor informações no topo do mapa base, tais como locais de interesse ou mesmo ruas. Combinar essas sobreposições para formar relacionamentos e rastreá-los ao longo do tempo podem ainda produzir aplicativos incrivelmente dinâmicos e capazes.

Representando dados espaciais

Independente das sobreposições ou outras informações associadas a um ou mais locais, os aplicativos de pesquisa precisam de uma forma para representar esses dados de forma eficiente. Embora as informações de local possam ser representadas de diversas maneiras, ficarei concentrado naquelas pertinentes ao Lucene. Em primeiro lugar, muitos tipos de dados geoespaciais podem ser representados em seu formato "bruto" e trabalhar perfeitamente com um aplicativo de pesquisa. Por exemplo, o Syracuse é uma forma perfeita de representar a cidade de Syracuse, e usuários que digitam Syracuse na caixa de pesquisa encontrarão os documentos que contêm Syracuse como qualquer outro termo de pesquisa. A representação bruta é, na verdade, a forma mais comum que as pessoas representam locais nomeados, tais como cidades, estados e códigos postais. Observe, contudo, que embora use a frase representação bruta, ainda é possível transformar ou normalizar os dados em primeiro lugar. Por exemplo, converter todas as menções de New York para NY é, frequentemente, uma coisa perfeitamente razoável a fazer.

Antes de falar sobre as representações que o Lucene pode usar, é importante entender que todas as representações devem levar em consideração a referência espacial que as produziu (consulte Recursos). Nos Estados Unidos, o mais comum é o World Geodetic System, abreviado como WGS 84 (consulte Recursos). Embora sejam possíveis transformações entre alguns sistemas, é melhor ter todos os seus dados representados em um único sistema. Daqui em diante, assumirei um único sistema.

As informações numéricas espaciais tais como latitude e longitude (lat/lon abreviado) são onde as representações mais interessantes entram no jogo em termos de pesquisa com o Lucene e Solr. Latitude e longitude são geralmente expressados em graus, minutos e segundos a partir do Meridiano Principal (localizado em Greenwhich, Inglaterra) e geralmente exige o uso de um double (ou mais) para fins de precisão. Por exemplo, para os dados incluídos em meu exemplo — a cidade de Syracuse, N.Y., Estados Unidos — está localizada cerca de 76.150026 Leste (ou -76.150026 se Leste não estiver especificado) e 43.049648 Norte.

Dependendo do aplicativo, a codificação de toda latitude e longitude pode resultar em um grande número de termos únicos a serem indexados. Isso não é necessariamente um empecilho, mas pode retardar significativamente a pesquisa, e como será possível ver mais adiante neste artigo, isso nem sempre é necessário. De fato, muitos aplicativos de mapeamento apenas tratam de vincular a pesquisa dentro de uma área específica, portanto, armazenar informações aproximadas sobre o local rende bem menos termos sem prejudicar os resultados da pesquisa. A abordagem de troca por precisão frequentemente captura latitude e longitude em camadas (Cartesianas). Pode-se pensar sobre cada camada como um nível ampliado de uma parte específica de um mapa, de modo que a camada 2 centralizada sobre os Estados Unidos provavelmente abrange toda a América do Norte, enquanto a camada 19 está provavelmente no quintal de alguém. Mais especificamente, cada camada divide o mapa em 2camada nº caixas ou grades. A cada caixa então pode ser dado um número e indexado no documento. Explicarei em uma seção posterior como alavancar essas informações para pesquisas mais rápidas.

A latitude e longitude em termos do Lucene são frequentemente representadas como dois campos diferentes, porém, em alguns aplicativos, isso pode ter implicações no desempenho. Se um único campo for desejado, lat/lon pode ser codificado em um único String usando a codificação Geohash (consulte Recursos). As Geohashes têm o benefício de precisão arbitrária pela eliminação de caracteres do fim do hash. Em muitos casos, os locais que estão próximos entre si possuem prefixos comuns. Por exemplo, inserir Syracuse, NY em geohash.org retorna o hash dr9ughxjkrt4b, enquanto inserir o subúrbio de Syracuse Cicero, NY retorna o hash dr9veggs4ptd3, ambos compartilhando o prefixo dr9.

Até agora, tratei especificamente de pontos, porém muitos aplicativos geoespaciais também estão interessados em formas, rotas e outros relacionamentos dentro dos dados. Esses estão além do escopo do que está disponível no Lucene e Solr; consulte Recursos para maiores informações sobre esses conceitos.


Combinar dados espaciais com texto em pesquisa

Uma vez que os dados são representados em um índice, os aplicativos de pesquisa geralmente possuem, pelo menos, cinco necessidades básicas quando se trata de interagir com os dados:

  • Cálculos de distância: Dado um ponto, calcule a distância para um ou mais outros pontos.
  • Filtro Caixa Delimitadora: Localize todas as ocorrências (documentos) dentro de alguma área específica.
  • Classificação: Classifique os resultados de uma pesquisa pela distância a partir de algum ponto fixo.
  • Aperfeiçoamento de relevância: Use a distância como um fator de reforço na pontuação ao mesmo tempo em que permite que outros fatores também desempenhem uma função.
  • Análise de consulta: Dado um endereço ou alguma outra especificação de usuário de um local, crie uma representação codificada que possa ser usada para pesquisar contra os dados indexados.

Cada uma dessas peças pode desempenhar um papel importante em aplicativos baseados em local, porém, por enquanto, nos concentraremos nos cálculos de distância, filtragem por caixa delimitadora e análise de consulta. A classificação e aperfeiçoamento de relevância (reforço) apenas usam cálculos de distância, e mostrarei como funcionam na prática mais adiante no artigo.

Cálculos de distância

Ao calcular distâncias para uso em aplicativos GIS, é importante compreender que há muitas abordagens diferentes, cada uma com seus próprios méritos e deméritos. Os cálculos de distância podem ser divididos em três grupos, dependendo de como um aplicativo escolhe modelar a Terra. Em alguns casos, é perfeitamente aceitável assumir um modelo plano da Terra e perder alguma precisão em troca de velocidade. Na abordagem de modelo plano, a maioria dos cálculos de distância se resume a variações no teorema de Pitágoras. A abordagem de modelo plano é, frequentemente, suficiente quando as distâncias são curtas e os locais não estão próximos dos pólos. Em outros casos, usa-se um modelo esférico, e o cálculo de distância primária usado é a distância de grande círculo (consulte Recursos). A distância de grande círculo calcula a menor distância entre dois pontos quaisquer na superfície de uma esfera. O modelo esférico é o mais adequado quando as distâncias estiverem mais separadas e for necessária maior precisão. Finalmente, um modelo elipsoidal da Terra pode ser usado juntamente com a fórmula de Vincenty (consulte Recursos) para obter distâncias altamente precisas (de até 0,5 milímetros) no elipsóide, porém para a maioria dos aplicativos, a complexidade deste cálculo provavelmente não valha a pena.

Dê um centímetro, receba um quilômetro

Em muitos aplicativos de pesquisa de local, a necessidade de precisão depende da aplicação. Em alguns casos, estar fora por um quilômetro não é problema, enquanto em outros casos estar fora por até poucos milímetros pode importar. Por exemplo, a distância Euclidiana não é, com frequência, precisa o suficiente para atravessar maiores distâncias (ou seja, entre dois estados), e mesmo a abordagem de Haversine (grande círculo) pode não ser precisa o suficiente em alguns casos, pois a Terra é melhor modelada como um elipsóide e não uma esfera. Nesses casos, usar a fórmula de Vincenty pode fazer mais sentido. Em outras aplicações, a única coisa que importa é a ordem dos resultados, portanto algo como a Distância Euclidiana Quadrada (que não é realmente uma distância) pode ser usada, economizando assim um cálculo de raiz quadrada.

Obviamente, outras distâncias são também muito úteis, tais como a distância de Manhattan, que reflete a distância em que alguém viaja através de uma cidade disposta em quarteirões (como em um táxi viajando através de Manhattan na Cidade de Nova York). Para os fins deste artigo, demonstrarei as distâncias usando o modelo de Terra plana e a distância de grande círculo e deixarei o restante para você explorar. Observe também que estou desconsiderando aqui a elevação como um fator, porém alguns aplicativos podem precisar contabilizá-la. Para mais informações sobre distâncias geográficas, consulte Recursos.

Filtro Caixa Delimitadora

Em muitos aplicativos baseados em local, milhões de dados de local estão disponíveis para serem pesquisados. Repetir todos esses dados apenas para localizar o conjunto de documentos que contenham as palavras-chave de interesse e também estejam dentro de uma certa distância do local especificado pelo usuário seria extremamente demorado. Naturalmente, faz mais sentido restringir primeiro o conjunto de documentos e então avaliar o subconjunto relevante. Se estiverem armazenadas apenas as informações de latitude e longitude, então a opção primária para restringir o conjunto de documento é inserir as faixas que abrangem a área em volta do local. Isto pode ser visualizado como na Figura 1, em que a caixa levemente opaca representa uma caixa delimitadora em volta da área da cidade de Charleston, S.C.:

Figura 1. Exemplo de uma caixa delimitadora baseado no centro de Charleston, S.C.
Exemplo de uma caixa delimitadora baseado no centro de Charleston, S.C.

Se o aplicativo também usa informações de camada ou informações Geohash, então estes valores podem ser usados para estreitar melhor o número de documentos para pesquisa. Demonstrarei isto posteriormente ao discutir os detalhes específicos da indexação e pesquisa com o Lucene e Solr.

Análise de consulta

A análise de consulta resulta em determinar que parte da consulta contém palavras-chaves para pesquisar e que parte contém informações de local. A última parte deste processo é denominada geocodificação (consulte Recursos). Embora eu vá discutir a geocodificação aqui no contexto da análise de consulta, ela também é útil durante a indexação. Considere os seguintes exemplos de consultas de usuário:

  • 1600 Pennsylvania Ave. Washington, DC
  • 1 Washington Av. Philadelphia Pennsylvania
  • Shopping da America, 60 East Broadway Bloomington, MN 55425
  • Restaurantes próximos ao Shopping da America
  • Restaurantes no Shopping da America

O exame das primeiras duas consultas levanta alguns pontos interessantes:

  • A ordem dos termos é quase sempre importante, enquanto que na pesquisa baseada em texto puro, a ordem pode não se importante.
  • Dicionários Geográficos e outros recursos espaciais como o GeoNames (consulte Recursos) podem ser muito úteis para converter endereços em locais. Estes recursos muitas vezes contêm listas de locais de interesse — por exemplo, marcos tais como a Casa Branca.
  • É importante normalizar as abreviaturas tais como Ave. e DC ou usar sinônimos para cobrir a variedade de formas em que os usuários fornecem informações de endereço.

As consultas restantes ilustram diversas outras sutilezas. Por exemplo, na terceira consulta, o usuário especificou um endereço completo; deve-se ter cuidado para analisar o nome, endereço, cidade, estado e código postal adequadamente se você vai pesquisar contra campos para cada uma dessas propriedades. Nas últimas duas consultas, a sutil diferença entre a opção do usuário de perto do versus no é provavelmente importante. Qualquer restaurante dentro de uma certa distância do Shopping seria adequado ao usuário da quarta consulta, enquanto que o usuário da última consulta só está interessado nos resultados dentro do Shopping. A análise de consulta pode ser bem difícil por causa da complexidade da descrição dos tópicos em relação ao local, para não falar nos erros de digitação, ambiguidade do texto, e dados incorretos.

Apesar de todas as complexidades da geocodificação, existem serviços disponíveis que traduzem endereços em locais. Dois serviços normalmente usados são a API pública do Google Maps e GeoNames (consulte Recursos). Infelizmente, usar esses serviços Web sujeita você a seus termos de uso (que muitas vezes incluem limites de uso) e preocupações com tráfego na Internet. Para sistemas reais de produção, provavelmente será melhor implementar suas próprias capacidades. Embora uma implementação dessas esteja fora do escopo deste artigo, tenha em mente que os dados do GeoNames podem ser baixados gratuitamente, assim como muitos outros recursos espaciais, tais como o Cia FactBook (consulte Recursos). Dados bons recursos, é melhor começar do básico (endereço, cidade, estado) e a seguir incluir locais de interesse e um robusto sistema de tratamento de exceções. Com o tempo, seus registros de consulta se mostrarão inestimáveis na criação de um robusto analisador de consultas que trate apropriadamente o que quer que seus usuários coloquem lá. Como ocorre com qualquer aplicativo de pesquisa, tenha em mente que é razoável fazer um melhor palpite enquanto também pede esclarecimento ao usuário, como se pode ver na captura de tela do Google Maps na Figura 2:

Figura 2. Melhor palpite e uma solicitação de esclarecimento do usuário no Google Maps
Melhor palpite e uma solicitação de esclarecimento do usuário no Google Maps

Para este artigo, demonstrarei um analisador de consulta básico que usa o serviço GeoNames e tem alguns outros recursos, mas deixarei para o leitor implementar uma versão pronta para produção. Neste ponto, você deve ter base suficiente para começar. Assim, o restante deste artigo se concentrará em como indexar e pesquisar informações espaciais usando o Lucene e o Solr.


Instalando o código de amostra

Para executar o código de amostra, são necessárias instalações do seguinte:

É necessário, também, o código de amostra deste artigo (consulte Download), que inclui uma cópia do Apache Solr e suas dependências. Siga esses passos para instalar o código de amostra:

  1. unzip sample.zip
  2. cd geospatial-examples
  3. ant install
  4. Launch Solr: ant start-solr (para parar o Solr posteriormente, execute ant stop-solr)
  5. Direcione seu navegador para http://localhost:8983/solr/admin e confirme se o Solr iniciou adequadamente. Deve-se ver uma tela admin básica com uma caixa para executar consultas.

Uma vez que o Solr esteja em funcionamento, você está pronto para dar os primeiros passos com dados espaciais no Lucene. Executar o passo de instalação vai efetuar o download de alguns dados de amostra gerados a partir do projeto OSM, que separei em http://people.apache.org/~gsingers/spatial/. Para este artigo, incluí dados de OSM de amostra provenientes de quatro locais dentro dos Estados Unidos que são de interesse para mim (Permalinks para o OSM estão listados nos arquivos):

  • Syracuse, N.Y.
  • Downtown Minneapolis, Minn.
  • Em torno do Shopping da America em Bloomington, Minn.
  • Centro de Charleston, S.C.

Para demonstrar muitos dos conceitos neste artigo, escrevi código para indexar os dados de OSM no Solr, e associar alguns fatos simples com locais específicos (por exemplo, consulte o arquivo syracuse.facts no diretório de dados.) A meta deste esforço é mostrar como texto não estruturado e dados espaciais podem ser combinados para criar eficientes aplicativos de pesquisa. Observe também que estou usando a versão Solr 1.5-dev (o tronco de desenvolvimento atual do Solr), não a recentemente lançada Solr 1.4.


Indexando informações espaciais no Lucene

O Lucene 2.9 adicionou dois novos recursos que desempenham um importante papel na pesquisa espacial. Primeiro, o Lucene implementou melhor consulta de faixa numérica e melhores capacidades de filtragem, que são frequentemente usadas para abordagens de caixa limitadora. Segundo, a Lucene tem um novo módulo contrib que contém um projeto individual anteriormente denominado Local Lucene (consulte Recursos). (O código reside em contrib/spatial do Lucene; Eu incluí o arquivo JAR com o código de amostra.) O spatial contrib oferece ferramentas para a criação de camadas cartesianas e códigos Geohash, assim como ferramentas para a criação de consulta Lucene e objetos de filtro.

Antes de ver o código que indexa os dados, é importante avaliar como você espera interagir com os dados e com que quantidade de dados você deverá lidar com seu aplicativo. Por exemplo, para a maioria das pessoas com número de documentos pequeno a moderado (digamos, menos de 10 milhões), a indexação da latitude e longitude e o uso de consultas simples de faixa numérica provavelmente produzirão desempenho suficiente, enquanto que aplicativos maiores podem precisar fazer mais coisas específicas (como por exemplo adicionar camadas cartesianas) para reduzir o número de termos e documentos a serem filtrados e pontuados. Também é importante pensar sobre em qual formato armazenar as informações. Muitos algoritmos de distância espacial exigem que os números sejam em radianos, enquanto outros podem trabalhar com graus. Assim, pode valer a pena converter seus valores de lat/lon em radianos durante a indexação em vez de ter de convertê-los várias vezes durante o tempo de pesquisa. O preço, obviamente, é mais espaço (disco e, possivelmente, memória) se precisar de ambos os formatos. Finalmente, você estará facetando, classificando e pontuando os recursos do local, em vez de apenas usá-los para filtragem? Se for o caso, então você também pode alternar representações.

Como este artigo é apenas para demonstrar os conceitos e não se destina para uso em produção, eu mostrarei como indexar s Geohash, camadas cartesianas e latitude e longitude todos em um local, em algum código Java de amostra. Para começar, defini diversos valores no esquema Solr (localizado em geospatial-examples/solr/conf/schema.xml) para capturar os dados de OSM. Os campos primários para local são mostrados na Listagem 1:

Listagem 1. Esquema de amostra Solr
<!-- Latitude -->
   <field name="lat" type="tdouble" indexed="true" stored="true"/>
<!-- Longitude -->
   <field name="lon" type="tdouble" indexed="true" stored="true"/>
<!--
   lat/lon in radians
   In a real system, use a copy field for these instead of sending over the wire -->
   <field name="lat_rad" type="tdouble" indexed="true" stored="true"/>
   <field name="lon_rad" type="tdouble" indexed="true" stored="true"/>
<!-- Hmm, what about a special field type here? -->
   <field name="geohash" type="string" indexed="true" stored="true"/>
<!-- Elevation data -->
   <field name="ele" type="tfloat" indexed="true" stored="true"/>
<!-- Store Cartesian tier information -->
   <dynamicField name="tier_*"  type="double" indexed="true"  stored="true"/>

Lucene e Solr

Embora eu esteja usando o esquema Solr para demonstrar os campos ao índice, todos os conceitos aqui estão disponíveis no Lucene também. Por exemplo, um tdouble é apenas a forma do Lucene 2.9.1 se referir a um NumericField com um passo de precisão de 8.

Estou armazenando os valores de lat/lon como campos tdouble. Um tdouble é um double representado internamente usando uma estrutura de Camada. Pode ser então usado pelo Lucene para reduzir significativamente o número de termos que precisam ser avaliados durante cálculos de faixa (caixa delimitadora), embora ele na verdade acrescente mais termos ao índice. Estou armazenando o Geohash como string simples (não analisada) porque só quero fazer resultado exato nela. A elevação, embora estritamente não necessária para os tipos de cálculos que estou fazendo, está armazenada como tfloat, que é apenas o float armazenado na estrutura de Camada. Finalmente, o campo dinâmico tier_* permite que o aplicativo adicione campos de camada cartesiana dinamicamente sem precisar prenunciar cada um. Deixarei para você explorar os outros campos de metadados capturados pelo processo de indexação.

O código responsável pela indexação dos dados está localizado na árvore de estrutura no arquivo sample.zip. A classe Driver é um utilitário de linha de comando para iniciar o processo de indexação, e a indexação real ocorre como parte de uma implementação de SAX ContentHandler denominada OSMHandler. Dentro do código do OSMHandler, as linhas-chave de interesse estão no método startElement(). Eu o dividirei em três seções. O primeiro exemplo, mostrado na Listagem 2, indexa a latitude e longitude como doubles e também os converte em radianos para indexação:

Listagem 2. Indexação de amostra de latitude/longitude
//... current is a SolrInputDocument
double latitude = Double.parseDouble(attributes.getValue("lat"));
double longitude = Double.parseDouble(attributes.getValue("lon"));
current.addField("lat", latitude);
current.addField("lon", longitude);
current.addField("lat_rad", latitude * TO_RADS);
current.addField("lon_rad", longitude * TO_RADS);

A indexação de lat/lon é bem simples. A seguir, indexo o valor de Geohash para o par lat/lon, conforme demonstrado na Listagem 3:

Listagem 3. Indexação de amostra de Geohash
//...
//See http://en.wikipedia.org/wiki/Geohash
String geoHash = GeoHashUtils.encode(latitude, longitude);
current.addField("geohash", geoHash);

No código do Geohash na Listagem 3, estou usando o método GeoHashUtils.encode() (há um método decode() equivalente) que vem com o pacote Lucene spatial contrib para converter o par lat/lon em uma única cadeia de caractere Geohash, que a seguir adiciono ao Solr. Finalmente, para adicionar suporte de camada cartesiana, eu fiz duas coisas no código OSMHandler:

  • No construtor, defini n instâncias da classe CartesianTierPlotter, uma para cada camada que desejo indexar.
  • No método startElement(), fiz um loop sobre os n plotters e obtive o identificador para cada elemento de grade que contém a latitude e longitude do elemento de OSM atual. O código para isso é mostrado na Listagem 4:
    Listagem 4. Indexação de amostra de camadas cartesianas
    //...
    //Cartesian Tiers
    int tier = START_TIER; //4
    //Create a bunch of tiers, each deeper level has more precision
    for (CartesianTierPlotter plotter : plotters)
       {current.addField("tier_" + tier, plotter.getTierBoxId(latitude, longitude));
    tier++;
    }

Tipicamente, uma consulta só precisa ocorrer contra uma camada por vez, portanto ter múltiplas camadas normalmente não é um problema. Você deve escolher o número de camadas de que precisa com base no nível de detalhamento que deseja usar em sua pesquisa. Se olhar atentamente ao restante do código de indexação, você verá que adicionei diversos outros valores de metadados referentes aos pontos de dados nos arquivos de OSM. Estou atualmente indexando apenas dois tipos de dados de OSM: um e uma via. Um nó é simplesmente um local em uma latitude e longitude específica, enquanto uma via é uma combinação de nós que estão todos de algum modo relacionados, como por exemplo uma rua. (Consulte o link OSM Data Primitives em Recursos para saber mais sobre os arquivos de OSM.)

O que é um CartesianTierPlotter?

O trabalho do CartesianTierPlotter é obter uma projeção da Terra (no meu caso, uso uma projeção senoidal; consulte Recursos) e as informações de lat/lon, convertê-la nas grades usadas pelo sistema de camadas, e dar a cada célula um número exclusivo. Durante a pesquisa, um aplicativo pode então especificar as IDs de grade para restringir a pesquisa para nela encontrar os resultados.

Agora que você tem uma compreensão básica da criação de um documento Solr que contém informações espaciais, só é necessário executá-lo. A classe Driver obtém os dados e arquivos de fato mais o URL em que o Solr está operando e passa o trabalho para a classe OSM2Solr. A classe OSM2Solr então usa o cliente Java do Solr, SolrJ, para obter os documentos criados pelo analisador SAX OSMHandler e os envia em lotes ao servidor Solr. Você pode executar a classe Driver por conta própria usando a linha de comando, ou você pode simplesmente executar ant index e o Ant fará o trabalho necessário para executar o driver. Ao terminar, direcione seu navegador para http://localhost:8983/solr/select/?q=*:* e verifique que o Solr encontrou 68.945 documentos. Dê uma olhada nos arquivos com calma e familiarize-se com o conteúdo.

Apenas toquei a superfície da enormidade de formas em que você pode classificar e organizar os dados de OSM, mas é hora de passar para a discussão de como aproveitar esses dados em um aplicativo.


Pesquisa por local

Agora que tenho dados no índice, é hora de relembrar os diferentes modos de usá-lo. A saber, demonstrarei como classificar, reforçar, e filtrar documentos com base em informações espaciais no índice.

Cálculos relacionados à distância

Reforçar e classificar documentos através da distância é um requisito comum para muitos aplicativos espaciais. Para essa finalidade, Lucene e Solr apresentam várias capacidades para calcular distâncias (consulte Recursos). O Lucene inclui ferramentas para classificação e filtragem com base na fórmula de grande círculo (Haversine) (consulte DistanceUtils e DistanceFieldComparatorSource), enquanto o Solr possui diversas funções FunctionQuery para calcular distâncias, inclusive:

  • Grande círculo (Haversine e Geohash Haversine)
  • Euclidiana e Euclidiana Quadrada
  • Manhattan e outras normas p

Reforço por distância é bem fácil usando as funções de distância do Solr. Ficarei concentrado nas consultas de função do Solr, pois elas são as mais fáceis de usar e não requerem programação para alavancar, mas podem ser facilmente usadas ou transportadas para o Lucene.

Conforme demonstrei anteriormente, tenho vários campos configurados para armazenar dados OSM, inclusive lat/lon, lat_rad/lon_rad e geohash. Posso, então, pesquisar e reforçar esses valores:

  • hsin (grande círculo): http://localhost:8983/solr/select/?q=name:Minneapolis AND _val_:"recip(hsin(0.78, -1.6, lat_rad, lon_rad, 3963.205), 1, 1, 0)"^100
  • dist (Euclidiana, Manhattan, norma p): http://localhost:8983/solr/select/?q=name:Minneapolis AND _val_:"recip(dist(2, lat, lon, 44.794, -93.2696), 1, 1, 0)"^100
  • sqedist (Euclidiana Quadrada): http://localhost:8983/solr/select/?q=name:Minneapolis AND _val_:"recip(sqedist(lat, lon, 44.794, -93.2696), 1, 1, 0)"^100
  • ghhdist (Geohash Haversine): http://localhost:8983/solr/select/?q=_val_:"recip (ghhsin(geohash(44.79, -93), geohash, 3963.205), 1, 1, 0)"^100

Em cada um desses casos, combinei uma consulta de palavra-chave com uma FunctionQuery baseada em distância para produzir um conjunto de resultado que fatore tanto a pontuação da palavra-chave como a pontuação da distância. Para visualizar os efeitos de cada uma dessas partes, adicione &debugQuery=true em cada consulta e passe um tempo examinando as explicações produzidas pelo Solr. Estes são apenas exemplos de seu uso. Para visualizar as assinaturas e documentação completas para essas e outras funções FunctionQuery, consulte Recursos. Obviamente, é possível escolher reforçar uma parte sobre a outra, ou de outro modo, alterar as chamadas para se adequar às suas necessidades.

Em relação à classificação por distância, o Solr oferece uma opção primária, que realmente uma solução provisória ao fato de que o Solr ainda não tem capacidades de classificação por função e ao fato de que não está definido nenhum FieldType neste ponto. Contudo, a solução provisória é simples. Para classificar por função, crie sua consulta conforme acima, porém zere, via reforço, a cláusula de palavra-chave, como em q=name:Minneapolis^0 AND _val_:.... Isso fará com que a classificação de palavra-chave seja zero (porém, os documentos compatíveis ainda serão retornados) e o valor de função será o único componente da pontuação. A prazo mais longo, procure pelo Solr para adicionar FieldTypes para melhor suporte de classificação, sem precisar zerar a consulta principal.

Com a classificação e a pontuação fora do caminho, é hora de avançar para a filtragem.

Filtragem

Para filtrar por local com o Solr, estão disponíveis os três mecanismos primários na Tabela 1 para gravadores de aplicativo para restringir o espaço do documento:

Tabela 1. Abordagens para filtragem
Abordagem de filtroDescriçãoExemplo
FaixaCrie um filtro de faixa que abranja a lat/lon da caixa delimitadora. Para razões de desempenho, é importante usar as capacidades TrieField (NumericField) do Solr com esta abordagem. http://localhost:8983/solr/ select/?q=*:*&fq=lon:[-80 TO -78]&fq=lat:[31 TO 33]
Camada cartesianaDada uma lat/lon e uma distância, identifique as células de grade ao redor do ponto central e restrinja-as apenas àqueles documentos que contêm essas células. Consulte O que é um QParserPlugin? para obter mais detalhes sobre sua implementação de fonte. http://localhost:8983/solr/ select/?q=*:*&fq={!tier x=32 y=-79 dist=50 prefix=tier_}
DistânciaUsando a capacidade QParserPluginfrange (função faixa) e uma função de distância (mais informações em Cálculos relacionados à distância, acima) do Solr, determine a distância entre os pontos e restrinja o espaço do documento. http://localhost:8983/solr/ select/?q=*:*&fq={!frange l=0 u=400}hsin(0.57, -1.3, lat_rad, lon_rad, 3963.205)

Algumas palavras sobre densidade

A densidade de dados em uma faixa específica geralmente desempenha um papel importante na experiência de pesquisa do usuário. Por exemplo, um aplicativo que fornece pesquisa de negócios para Manhattan em Nova York, N.Y. é muito mais denso do que um que fornece resultados para Buffalo, Minn. (consulte Recursos). De fato, pode ser útil incorporar essa informação em sua função de filtragem, de modo que o aplicativo escolha uma distância eficaz para garantir bons resultados. Infelizmente, demonstrar como fazer isso está além do escopo deste artigo.

Qual é a abordagem certa para você? Isso dependerá da densidade de seus pontos (consulte Algumas palavras sobre densidade), porém uma boa recomendação é começar com a abordagem de faixa simples e então avançar para a abordagem de camada, se necessário. O fator fundamental é observar o número de termos que precisam ser avaliados de uma única vez ao calcular a faixa, pois esse número é o que controla diretamente a carga de trabalho que o Lucene deve realizar para restringir o conjunto de resultado.

Um analisador de consulta geonames.org simples

Construir um analisador de consulta completo para espacial está além do escopo deste artigo. Em vez disso, construirei um QParserPlugin simples que tratará das tarefas de obtenção de resultados a partir das informações de local provenientes do GeoNames. Este analisador presume que um aplicativo possa dividir a entrada de usuário antes do tempo em duas partes: a consulta de palavra-chave e a consulta espacial. De fato, muitos aplicativos de pesquisa local solicitam ao usuário a entrada apenas desse modo através de duas caixas de entrada.

O que é um QParserPlugin?

Um QParserPlugin é linguagem Solr de um módulo plug-in de analisador de consulta. Assim como muitas partes do Solr são plugáveis, também são as implementações do analisador de consulta. Para este artigo, estou usando três diferentes plug-ins de analisador de consulta, um que apresenta — FunctionRangeQParserPlugin ({!frange})— do Solr e dois que escrevi: CartesianTierQParserPlugin ({!tier}) e o GeonamesQParserPlugin. A fonte dos dois plug-ins está localizada sob a árvore src no download de exemplo. Ambos os plug-ins já estão configurados no Solr através do arquivo solrconfig.xml: QParserPlugins são chamados na consulta, especificando-se {!parserName [parameters]}[query], (os parâmetros e a consulta podem ser opcionais), como em {!tier x=32 y=-79 dist=50 prefix=tier_} e {!frange l=0 u=400}hsin(0.57, -1.3, lat_rad, lon_rad, 3963.205).

O analisador pode adotar vários parâmetros:

  • topo: Abreviação de topônimo (consulte a documentação GeoNames). O local de pesquisa em GeoNames. Obrigatório.
  • fileiras: O número de fileiras para retornar do GeoNames. Opcional. O padrão é 1.
  • início: O resultado para iniciar. Opcional. O padrão é 0.
  • lat: O campo latitude para usar como um ValueSource para o FunctionQuery. Se especificado, lon também deve ser definido.
  • lon: O campo longitude para usar como um ValueSource para o FunctionQuery. Se especificado, lat também deve ser definido.
  • gh: O campo Geohash para usar como um ValueSource para o FunctionQuery. Se especificado, lat/lonnão deve ser definido.
  • dist: A função de distância a ser usada. String. Um dos [hsin, 0-Integer.MAX_VALUE, ghhsin]. Se for especificado um campo geohash, este campo, então, é desconsiderado e ghhsin é automático. O padrão é 2 para a norma-2 (Euclidiana).
  • unidade - KM|M: As unidades a serem usadas, KM para métrica, M para Inglês. O padrão é M.
  • boost - float: O valor através do qual a função é reforçada. O padrão é 1.

O código para este exemplo está localizado em GeonamesQParserPlugin.java no download de exemplo. (O servidor Solr já está configurado na versão Solr inclusa no download.) Chamá-lo é bastante parecido com chamar o CartesianTierQParserPlugin descrito acima. Por exemplo, para pesquisar shopping centers no índice relativo a Bloomington, Minn., usei http://localhost:8983/solr/select/?q=text:mall AND _query_:"{!geo topo='Bloomington, MN' lat=lat_rad lon=lon_rad dist=hsin}".

Adotando a abordagem QParserPlugin, pude concentrar-me em tratar apenas a sintaxe específica que foi importante para mim, enquanto o conhecimento do local ainda permitia que todas as capacidades de análise de consulta baseada em texto procedessem como de costume.

A partir daqui, o GeonamesQParserPlugin poderia ser expandido de modo considerável para trabalhar com códigos postais e muitas outras especificações de local. Naturalmente, ele também precisa de mais tratamento de erros e provavelmente precisa ser convertido para usar o dataset do GeoNames (consulte Recursos) de modo que ele não dependa de chamadas de serviços Web. O Solr também possui um problema pendente em seu rastreador de problemas para adicionar suporte de analisador de consulta (consulte Recursos).


Para onde prosseguir?

Demonstrei as capacidades do Lucene e do Solr para pesquisar, classificar e filtrar documentos de texto com base em um modelo de local baseado em pontos. A partir daqui, será necessário um aplicativo de pesquisa local para investigar o melhor modo de escalar, tratar consultas de usuário e visualizar os resultados. Para escalar, algumas questões são respondidas por meio de quantos termos precisam ser enumerados quando é criado o filtro da caixa delimitadora. Além da questão de filtro para escalação, serão aplicados os fatores de costume relacionados a pesquisa, tal como sobre distribuir o índice ou simplesmente replicá-lo. Consulte os Recursos do Lucene e do Solr.

Se você tiver interesse em construir um aplicativo GIS mais significativo, será preciso adicionar capacidades muito mais sofisticadas para localização de rota, intersecção de formas e muito mais. Contudo, se você precisa construir um sólido aplicativo de pesquisa que combine a estrutura de locais baseados em ponto com texto não estruturado, então, não procure além do Lucene e do Solr.

Agradecimentos

Agradecimentos especiais para os desenvolvedores do Lucene/Solr Ryan McKinley e Yonik Seeley por suas contribuições e revisão deste artigo.


Download

DescriçãoNomeTamanho
Spatial examplesj-spatial.zip52.4 MB

Recursos

Aprender

Obter produtos e tecnologias

Discutir

Comentários

developerWorks: Conecte-se

Los campos obligatorios están marcados con un asterisco (*).


Precisa de um ID IBM?
Esqueceu seu ID IBM?


Esqueceu sua senha?
Alterar sua senha

Ao clicar em Enviar, você concorda com os termos e condições do developerWorks.

 


A primeira vez que você entrar no developerWorks, um perfil é criado para você. Informações no seu perfil (seu nome, país / região, e nome da empresa) é apresentado ao público e vai acompanhar qualquer conteúdo que você postar, a menos que você opte por esconder o nome da empresa. Você pode atualizar sua conta IBM a qualquer momento.

Todas as informações enviadas são seguras.

Elija su nombre para mostrar



Ao se conectar ao developerWorks pela primeira vez, é criado um perfil para você e é necessário selecionar um nome de exibição. O nome de exibição acompanhará o conteúdo que você postar no developerWorks.

Escolha um nome de exibição de 3 - 31 caracteres. Seu nome de exibição deve ser exclusivo na comunidade do developerWorks e não deve ser o seu endereço de email por motivo de privacidade.

Los campos obligatorios están marcados con un asterisco (*).

(Escolha um nome de exibição de 3 - 31 caracteres.)

Ao clicar em Enviar, você concorda com os termos e condições do developerWorks.

 


Todas as informações enviadas são seguras.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=80
Zone=Tecnologia Java, Software livre
ArticleID=471435
ArticleTitle=Pesquisa ciente de local com Apache Lucene e Solr
publish-date=03042010