Título: Bidirectional Search for Nearest Neighbors Queries over Road Networks

Data: 17/08/2017 Horário: 14h Local: Sala de Seminários - Bloco 952 - Campus do Pici

Resumo:

O presente trabalho estuda a consulta dos k vizinhos mais próximos em redes de ruas estáticas, considerando Pontos de Interesse Voláteis (PoI-V). Esse novo tipo de PoI tem uma alta frequência de atualização de localização em um mapa e sua disponibilidade é incerta. Aplicações de compartilhamento de caronas representam um bom exemplo de uso dessa consulta: motoristas podem tornar-se disponíveis ou indisponíveis a qualquer momento para aceitarem uma chamada ou ter suas localizações alteradas com frequência. Soluções anteriores utilizam índices espaciais ou demandam uma fase de pré-processamento no algoritmo, fazendo com que as suas utilizações com PoI-V's sejam inviáveis uma vez que se um desses objetos tornar-se disponível ou indisponível, o pré-processamento ou o índice deverão ser refeitos. A solução proposta utiliza o algoritmo A* para direcionar a expansão dos vértices, bem como uma busca bidirecional a partir do ponto de consulta e dos PoI-V's. Técnicas de poda de espaço de busca também são aplicadas para diminuir a quantidade de potenciais PoI-V's a serem verificados. A corretude e a construção do algoritmo são apresentadas, assim como uma avaliação experimental empírica com redes de ruas reais.

Banca:

• Prof. Dr. José Antônio Fernandes de Macêdo (MDCC/UFC - Orientador)
• Prof. Mário Antonio do Nascimento (UA/Canadá - Coorientador)
• Prof.ª Dr.ª Ticiana Linhares Coelho da Silva (UFC)
• Prof. Dr. Javam de Castro Machado (MDCC/UFC)