Energy-efficient air-indices for shortest path and distance queries on road networks

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

2 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)182-198
Journal / PublicationInformation Systems
Online published30 Aug 2017
Publication statusPublished - Nov 2017


Although various air-indices, e.g., Next Region (NR), have been proposed to support shortest path and distance queries at mobile clients on a road network, how to minimize the energy cost, which is dominated by the cost for obtaining traffic data from data broadcast, is still one of the most important performance objectives. Inspired by various preprocessing schemes in traditional computation models for shortest path queries that make use of special properties of road networks, we design in this paper a new air-index called the CH Index with the purpose of minimizing the energy cost for obtaining broadcasting data to perform shortest path and distance queries at mobile clients. Experimental evaluation shows that our CH Index is more energy efficient than the state-of-the-art index NR by an order of magnitude. We also extend the CH Index to the CHBN Index which provides a tradeoff between energy efficiency and response time for obtaining traffic data via a user-tunable parameter. We show that CHBN gives shorter response time than CH while still being energy efficient.

Research Area(s)

  • Contraction hierarchy, Shortest distance query, Shortest path query, Wireless data broadcast