Trip Planning Queries in Indoor Venues

In this paper, we study a new type of indoor queries, called the indoor trip planning query (iTPQ). We have observed that the existing methods for outdoor spaces cannot be applied directly to indoor spaces, due to the difference in the underlying networks. Outdoor spaces, which are normally represented as spatial road networks, are commonly modelled as a graph. In contrast, indoor spaces have distinct features (e.g. rooms, doors, hallways) that do not exist in road networks. So far, no specific solutions have been proposed for iTPQ. Even if outdoor techniques are revised for iTPQ, they fail to process iTPQ efficiently. In this paper, we propose an indoor-specific technique, based on the indoor VIP-Tree, called the VIP-Tree neighbor expansion (VNE) method, that also includes new pruning techniques in both pre-processing and query processing phases. Our experimental results show that our proposed method VNE outperforms other indoor and outdoor algorithms by several orders of magnitude in terms of processing time with low indexing cost.