Shortest Path Computation on Air Indexes

• Main Authors: KELLARIS, Georgios, MOURATIDIS, Kyriakos
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2010
• Subjects: Air indexes; Device specification; Location dependents; Network industries; Real road networks; Road network; Shortest path; Shortest path computations; Spatial problems; Transportation network; Wireless broadcast; Databases and Information Systems; Numerical Analysis and Scientific Computing
• Online Access: https://ink.library.smu.edu.sg/sis_research/615; https://ink.library.smu.edu.sg/context/sis_research/article/1614/viewcontent/VLDB10_SPAirIndex.pdf
• Institution: Singapore Management University

Shortest path computation is one of the most common queries in location-based services that involve transportation net- works. Motivated by scalability challenges faced in the mo- bile network industry, we propose adopting the wireless broad- cast 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 rst framework to compute shortest paths on the air, and demonstrate the practicality and e ciency of our techniques through exper- iments with real road networks and actual device speci ca- tions.