Time-constrained indoor keyword-aware routing: foundations and extensions

With the increasingly available indoor positioning technologies, indoor location-based services (LBS) are becoming popular. Among indoor LBS applications, indoor routing is particularly in demand. In the literature, there are several existing studies on indoor keyword-aware routing queries, each considering different criteria when finding an optimal route. However, none of these studies explicitly constraint the time budget for the route. In this paper, we propose a new problem formulation TIKRQ that considers the time needed for a user to complete the route, in addition to other criteria such as static cost and textual relevance. A set-based search algorithm and effective pruning strategies are proposed as the foundations of processing TIKRQ. To further enhance the practicability of TIKRQ, we study the extensions of TIKRQ and propose efficient solutions. First, we present two TIKRQ variants, namely preferred visiting order and absence of a target point. Second, we present a session-based TIKRQ that keeps track of and refines a user’s routing results when the user changes the query parameters. We conduct extensive experiments on both real and synthetic datasets to verify the efficiency of our proposals.