Proceedings of the VLDB Endowment · 2010 · 31 citations · 13 references
ComputingComputer ScienceComputer SystemsAlgorithmsComputer NetworksMobile ComputingMobile Ad Hoc NetworksMobile NetworkingMobile NetworksRoutingShortest Path AlgorithmsWireless NetworksBroadcastIndexesLocation-based ServicesPath ComputationScalabilityShortest Path On Road NetworksShortest PathsWireless Broadcast Channels
Shortest path computation is one of the most common queries in location-based services that involve transportation networks. Motivated by scalability challenges faced in the mobile network industry, we propose adopting the wireless broadcast model for such location-dependent applications. In this model the data are continuously transmitted on the air, while clients listen to the broadcast and process their queries locally. Although spatial problems have been considered in this environment, there exists no study on shortest path queries in road networks. We develop the first framework to compute shortest paths on the air, and demonstrate the practicality and efficiency of our techniques through experiments with real road networks and actual device specifications.
13
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
Computing the shortest path: A search meets graph theory
Andrew V. Goldberg, Chris Harrelson · 2005 · 728 citations
An energy efficient MAC protocol for wireless LANs
Eun-Sun Jung, Nitin H. Vaidya · 2003 · 364 citations