With the advances in geo-positioning technologies and location-based services, it is nowadays quite common for road networks to have textual contents on the vertices. Previous work on identifying an optimal route that covers a sequence of query keywords has been studied in recent years. However, in many practical scenarios, an optimal route might not always be desirable. For example, a personalized route query is issued by providing some clues that describe the spatial context between Pose along the route, where the result can be far from the optimal one. Therefore, in this paper, we investigate the problem of clue-based route search (CRS), which allows a user to provide clues on keywords and spatial relationships. First, we propose a greedy algorithm and a dynamic programming algorithm as baselines. To improve efficiency, we develop a branch-and-bound algorithm that prunes unnecessary vertices in query processing. In order to quickly locate candidate, we propose an AB-tree that stores both the distance and keyword information in tree structure. To further reduce the index size, we construct a PB-tree by utilizing the virtue of 2-hop label index to pinpoint the candidate. Extensive experiments are conducted and verify the superiority of our algorithms and index structures.

Spatial keyword queries, clue, Point-of-Interest, travel route search, query processing

[1] I. Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck. Hierarchical hub labelings for shortest paths. In ESA, pages 24–35. Springer, 2012.
[2] T. Akiba, Y. Iwata, K.-i. Kawarabayashi, and Y. Kawata. Fast shortestpath distance queries on road networks by pruned highway labeling. In ALENEX, pages 147–154. SIAM, 2014.
[3] T. Akiba, Y. Iwata, and Y. Yoshida. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In SIGMOD, pages 349–360. ACM, 2013.
[4] T. Akiba, Y. Iwata, and Y. Yoshida. Dynamic and historical shortestpath distance queries on large evolving networks by pruned landmark labeling. In WWW, pages 237–248. ACM, 2014.
[5] J. L. Bentley and J. B. Saxe. Decomposable searching problems i. staticto-dynamic transformation. Journal of Algorithms, 1(4):301–358, 1980.
[6] X. Cao, L. Chen, G. Cong, and X. Xiao. Keyword-aware optimal route search. PVLDB, 5(11):1136–1147, 2012.
[7] X. Cao, G. Cong, and C. S. Jensen. Retrieving top-k prestige-based relevant spatial web objects. PVLDB, 2010.
[8] X. Cao, G. Cong, C. S. Jensen, and B. C. Ooi. Collective spatial keyword querying. In SIGMOD, pages 373–384. ACM, 2011.
[9] H. Chen, W.-S. Ku, M.-T. Sun, and R. Zimmermann. The multi-rule partial sequenced route query. In SIGSPATIAL, page 10. ACM, 2008.
[10] L. Chen, G. Cong, C. S. Jensen, and D. Wu. Spatial keyword query processing: an experimental evaluation. PVLDB, 2013.
[11] N. Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, DTIC Document, 1976.
[12] G. Cong, C. S. Jensen, and D. Wu. Efficient retrieval of the top-k most relevant spatial web objects. PVLDB, 2009.
[13] I. De Felipe, V. Hristidis, and N. Rishe. Keyword search on spatial databases. In ICDE, 2008. [14] E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik, 1(1):269–271, 1959.
[15] T. Guo, X. Cao, and G. Cong. Efficient algorithms for answering the m-closest keywords query. In SIGMOD, pages 405–418. ACM, 2015. [16] C. S. Jensen, J. Kola´ˇrvr, T. B. Pedersen, and I. Timko. Nearest neighbor queries in road networks. In GIS, pages 1–8. ACM, 2003.
[17] M. Jiang, A. W.-C. Fu, and R. C.-W. Wong. Exact top-k nearest keyword search in large networks. In SIGMOD, pages 393–404. ACM, 2015. [18] M. Jiang, A. W.-C. Fu, R. C.-W. Wong, and Y. Xu. Hop doubling label indexing for point-to-point distance querying on scale-free networks. PVLDB, 7(12):1203–1214, 2014.
[19] Y. Kanza, R. Levin, E. Safra, and Y. Sagiv. Interactive route search in the presence of order constraints. PVLDB, 3(1-2):117–128, 2010.
[20] Y. Kanza, E. Safra, Y. Sagiv, and Y. Doytsher. Heuristic algorithms for route-search queries over geographical data. In SIGSPATIAL, page 11. ACM, 2008.
[21] K. C. Lee, W.-C. Lee, and B. Zheng. Fast object search on road networks. In EDBT, 2009.
[22] F. Li, D. Cheng, M. Hadjieleftheriou, G. Kollios, and S.-H. Teng. On trip planning queries in spatial databases. In SSTD, pages 273–290. Springer, 2005.
[23] G. Li, J. Feng, and J. Xu. Desks: Direction-aware spatial keyword search. In ICDE, 2012.
[24] J. Li, Y. D. Yang, and N. Mamoulis. Optimal route queries with arbitrary order constraints. TKDE, 25(5):1097–1110, 2013.
[25] J. Liu, K. Deng, H. Sun, Y. Ge, X. Zhou, and C. S. Jensen. Clue-based spatio-textual query. PVLDB, 10(5), 2017.
[26] C. Long, R. C.-W. Wong, K. Wang, and A. W.-C. Fu. Collective spatial keyword queries: a distance owner-driven approach. In SIGMOD, pages 689–700. ACM, 2013.
[27] J. B. Rocha-Junior and K. Nørvag. Top-k spatial keyword queries on ˚ road networks. In EDBT, pages 168–179. ACM, 2012.
[28] M. Sharifzadeh, M. Kolahdouzan, and C. Shahabi. The optimal sequenced route query. VLDBJ, 17(4):765–787, 2008.
[29] B. Yao, M. Tang, and F. Li. Multi-approximate-keyword routing in gis data. In SIGSPATIAL, pages 201–210. ACM, 2011.
[30] C. Zhang, H. Liang, K. Wang, and J. Sun. Personalized trip recommendation with poi availability and uncertain traveling time. In CIKM, pages 911–920. ACM, 2015.
[31] D. Zhang, Y. M. Chee, A. Mondal, A. K. Tung, and M. Kitsuregawa. Keyword search in spatial databases: Towards searching by document. In ICDE, pages 688–699. IEEE, 2009.
[32] D. Zhang, B. C. Ooi, and A. K. Tung. Locating mapped resources in web 2.0. In ICDE, pages 521–532. IEEE, 2010.
[33] B. Zheng, N. J. Yuan, K. Zheng, X. Xie, S. Sadiq, and X. Zhou. Approximate keyword search in semantic trajectory database. In ICDE, pages 975–986. IEEE, 2015.
[34] B. Zheng, K. Zheng, X. Xiao, H. Su, H. Yin, X. Zhou, and G. Li. Keyword-aware continuous knn query on road networks. In ICDE, pages 871–882. IEEE, 2016.
[35] K. Zheng, S. Shang, N. J. Yuan, and Y. Yang. Towards efficient search for activity trajectories. In ICDE, pages 230–241. IEEE, 2013.
[36] R. Zhong, G. Li, K.-L. Tan, and L. Zhou. G-tree: An efficient index for knn search on road networks. In CIKM, 2013.