Keyword-aware Skyline Routes Search in Indoor Venues
Chaluka Salgado · 2018
Route planning has been extensively studied in the past few years due to its real-world applications. A route planning query returns an optimal route that starts from the source location, passes through at least one location from each given preference (specified by keywords) and ends at the target location. In this study, we introduce a new interesting route planning problem called keyword-aware skyline routes (KSR) query which returns a set of non-dominated routes, i.e., skyline routes, instead of an optimal route. Two attributes, namely the route distance and the number of shops/stores visited are taken into account in determining the dominance of a route over another route. Hence, KSR query assists the user in finding the most suitable route among the skyline routes based on the aforementioned dimensions. Although we prove that the problem of KSR query is NP-hard, we propose an efficient exact solution for the case when the number of query keywords is small which is typically the case in the real-world applications. We present an extensive experimental study on a large real-world shopping centre containing real products. Our experimental study shows the efficiency and the scalability of our algorithm.