Shortest Path Queries for Indoor Venues with Temporal Variations

Tiantian Liu, Zijin Feng, Huan Li, Hua Lu, Muhammad Aamir Cheema, Hong Cheng, Jianliang Xu

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


The recent years have witnessed the growing popularity of indoor location-based services (LBS) in practice and research. Among others, indoor shortest path query (ISPQ) is of fundamental importance for indoor LBS. However, existing works on ISPQ ignore indoor temporal variations, e.g., the open and close times associated with entities like doors and rooms. In this paper, we define a new type of query called Indoor Temporal-variation aware Shortest Path Query (ITSPQ). It returns the valid shortest path based on the up-to-date indoor topology at the query time. A set of techniques is designed to answer ITSPQ efficiently. We design a graph structure (IT-Graph) that captures indoor temporal variations. To process ITSPQ using IT-Graph, we design two algorithms that check a door's accessibility synchronously and asynchronously. We evaluate the proposed techniques using extensive experiments on synthetic and real data. The results show that our methods are efficient.
Original languageEnglish
Title of host publicationThe 36th IEEE International Conference on Data Engineering (ICDE 2020)
Place of PublicationUSA
Publication date2020
ISBN (Electronic)978-1-7281-2903-7
Publication statusPublished - 2020
Externally publishedYes
Event36th IEEE International Conference on Data Engineering - Online, Dallas, United States
Duration: 20 Apr 202024 Apr 2020
Conference number: 36


Conference36th IEEE International Conference on Data Engineering
Country/TerritoryUnited States
OtherOnline conference
Internet address

Bibliographical note

36th IEEE International Conference on Data Engineering, ICDE 2020 ; Conference date: 20-04-2020 Through 24-04-2020


  • Indoor routing
  • Temporal-variation
  • Shortest path algorithm

Cite this