Towards Indoor Temporal-variation aware Shortest Path Query

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

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

4 Citations (Scopus)


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 doors accessibility synchronously and asynchronously. Furthermore, we propose a novel index structure (IT-Index) that extends the state-of-the-art index significantly by storing dynamic door-to-door distances in a compact distance cube associated with tree nodes. When processing ITSPQ using IT-Index, we make use of the distance cube to avoid time-consuming indoor distance computation on-the-fly. We evaluate the proposed techniques using extensive experiments on synthetic and real data. The results show that our IT-Index based method is the most efficient for processing ITSPQ at a modest cost of index memory consumption.

Original languageEnglish
Pages (from-to)998-1012
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number1
Early online date27 Apr 2021
Publication statusPublished - 1 Jan 2023

Scopus Subject Areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

User-Defined Keywords

  • indoor space indexing
  • shortest path query
  • Temporal variation


Dive into the research topics of 'Towards Indoor Temporal-variation aware Shortest Path Query'. Together they form a unique fingerprint.

Cite this