Time-Constrained Sequenced Route Query in Indoor Spaces
Location-based services (LBSs) in indoor spaces have emerged as a new research direction.In this paper,we study a new kind of indoor LBSs that is called Time-Constrained Sequenced Route (TCSR) query.A TCSR query returns a route consisting of a sequence of indoor locations before a given deadline such that each location matches a given location type as well as a given stay-time period.Such queries are popular in indoor spaces,e.g.,in a business center,people may want to first stay at a toy shop for 30 min,and then go to a coffee room for one-hour rest,and finally arrive at a cinema before 18:00 PM.Classic route-search algorithms like Dijkstra have to search a large set of possible routes and thus are inefficient for TCSR queries.In addition,they do not consider the multi-floor feature of indoor spaces.In this paper we present a two-stage approach to evaluate a TCSR query.First,we find the optimal floor sequence for a TCSR query.Next,we propose a multi-source Dijkstra algorithm to get the time-constrained sequenced locations in a single floor.We conduct experiments on a synthetic indoor space and the results suggest that our proposal is efficient and scalable.
Indoor space Route query Time constraint
Wenyi Luo Peiquan Jin Lihua Yue
School of Computer Science and Technology,University of Science and Technology of China,Hefei 230027 School of Computer Science and Technology,University of Science and Technology of China,Hefei 230027
国际会议
International Asia-Pacific Web Conference(第18届国际亚太互联网大会)
苏州
英文
129-140
2016-09-23（万方平台首次上网日期，不代表论文的发表时间）