Um estudo experimental sobre algoritmos de caminho mais curto baseados em rotulagem de hub

A recuperação da distância do caminho mais curto é um componente central em muitas aplicações importantes. Durante uma década, as técnicas de rotulagem de hub (HL) foram consideradas uma solução prática com tempo de resposta de consulta rápido (por exemplo, 1--3 ordens de magnitude mais rápido), tempo de indexação competitivo e sobrecarga de armazenamento ligeiramente maior (por exemplo, várias vezes maior). Essas técnicas aumentam o throughput de consultas em até centenas de milhares de consultas por segundo, o que é particularmente útil em ambientes com muitos usuários. Apesar da importância das técnicas de HL, não temos conhecimento de nenhum estudo experimental abrangente sobre as técnicas de HL. Assim, é difícil para um praticante adotar as técnicas de HL para suas aplicações. Para abordar as questões acima, fornecemos um estudo experimental abrangente sobre a técnica de HL mais avançada, com análise de sua eficiência, eficácia e aplicabilidade. A partir de um resumo perspicaz de diferentes técnicas de HL, desenvolvemos uma técnica de HL simples, mas eficaz, chamada Hub Pushing baseado em Caminhos Significativos (SHP), que melhora significativamente o tempo de indexação das técnicas anteriores, mantendo um bom desempenho nas consultas. Também complementamos extensas comparações entre técnicas de HL e outras soluções de caminho mais curto para demonstrar a robustez e a eficiência das técnicas de HL.