Bidirectional search for nearest neighbors queries over road networks
Luís Gustavo Coutinho do Rêgo · 2017
O presente trabalho estuda a consulta dos k vizinhos mais proximos em redes de ruas estaticas, considerando Pontos de Interesse Volateis (PoI-V). Esse novo tipo de PoI tem uma alta frequencia de atualizacao de localizacao em um mapa e sua disponibilidade e incerta. Aplicacoes de compartilhamento de caronas representam um bom exemplo de uso dessa consulta: motoristas podem tornar-se disponiveis ou indisponiveis a qualquer momento para aceitarem uma chamada ou ter suas localizacoes alteradas com frequencia. Solucoes anteriores utilizam indices espaciais ou demandam uma fase de pre-processamento no algoritmo, fazendo com que as suas utilizacoes com PoI-V’s sejam inviaveis uma vez que se um desses objetos tornar-se disponivel ou indisponivel, o pre-processamento ou o indice deverao ser refeitos. A solucao proposta utiliza uma combinacao do algoritmo A* com uma busca bidirecional, direcionando a expansao dos vertices, bem como diminuindo o tempo de processamento da consulta. Tecnicas de poda de espaco de busca tambem sao aplicadas para reduzir a quantidade de potenciais PoI-V’s a serem verificados. A corretude e a construcao do algoritmo sao apresentadas, assim como uma avaliacao experimental empirica com redes de ruas reais.