SALT. A Unified Framework for All Shortest-Path Query Variants on Road Networks Full text

Alexandros Efentakis, Dieter Pfoser, Yannis Vassiliou
14th International Symposium on Experimental Algorithms (SEA 2015)
Abstract. Although recent scientific literature focuses on multiple shortest-path (SP) problem definitions for road networks, none of the existing solutions can efficiently answer all the different SP query variations. This work proposes SALT, a novel framework that not only efficiently answers most SP queries but also k-nearest neighbor queries not tackled by previous methods. Our solution offers excellent query performance and very short preprocessing times, thus making it also a viable option for dynamic, live-traffic road networks and all types of practical use-cases. The proposed SALT framework is a deployable software solution capturing a range of graph-related query problems under one “algorithmic hood”