{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,9]],"date-time":"2025-07-09T22:59:14Z","timestamp":1752101954425,"version":"3.41.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,6,23]],"date-time":"2023-06-23T00:00:00Z","timestamp":1687478400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation SWIFT","award":["2030249"],"award-info":[{"award-number":["2030249"]}]},{"name":"National Science Foundation AitF","award":["CCF-1637541"],"award-info":[{"award-number":["CCF-1637541"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2023,9,30]]},"abstract":"<jats:p>\n            Recommending a Point of Interest (PoI) or a sequence of PoIs to visit based on user\u2019s preferences and geo-locations has been one of the most popular applications of Location-Based Services (LBS). Variants have also been considered which take other factors into consideration, such as broader (implicit or explicit) semantic constraints as well as the limitations on the length of the trip. In this work, we present an efficient algorithmic solution to a novel query \u2013\n            <jats:bold>PaDOC<\/jats:bold>\n            (Paths with Distance, Origin, and Category constraints) \u2013 which combines the generation of a path that (a) can be traversed within a user-specified budget (e.g., limit on distance), (b) starts at one of the user-specified origin locations (e.g., a hotel), and (c) contains PoIs from a user-specified list of PoI categories. We show that the problem of deciding whether such a path exists is an NP-hard problem. Based on a novel indexing structure, we propose two efficient algorithms for approximate\n            <jats:bold>PaDOC<\/jats:bold>\n            query processing based on both conservative and progressive distance estimations. We conducted extensive experiments over real, publicly available datasets, demonstrating the benefits of the proposed methodologies over straightforward solutions.\n          <\/jats:p>","DOI":"10.1145\/3596601","type":"journal-article","created":{"date-parts":[[2023,5,8]],"date-time":"2023-05-08T12:19:20Z","timestamp":1683548360000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Distance, Origin and Category Constrained Paths"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5169-1425","authenticated-orcid":false,"given":"Xu","family":"Teng","sequence":"first","affiliation":[{"name":"Electrical and Computer Engineering, Iowa State University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8839-6278","authenticated-orcid":false,"given":"Goce","family":"Trajcevski","sequence":"additional","affiliation":[{"name":"Electrical and Computer Engineering, Iowa State University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7001-4123","authenticated-orcid":false,"given":"Andreas","family":"Z\u00fcfle","sequence":"additional","affiliation":[{"name":"Computer Science, Emory University, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,23]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516462"},{"key":"e_1_3_1_3_2","volume-title":"ACM GIS","author":"Alvares Luis Otavio","year":"2007","unstructured":"Luis Otavio Alvares, Vania Bogorny, Bart Kuijpers, Jose Antonio Fernandes de Macedo, Bart Moelans, and Alejandro Vaisman. 2007. A model for enriching trajectories with semantic geographical information. In ACM GIS."},{"key":"e_1_3_1_4_2","volume-title":"Location-Based Recommendation Systems","author":"Bao Jie","year":"2017","unstructured":"Jie Bao and Yu Zheng. 2017. Location-Based Recommendation Systems. Springer."},{"issue":"3","key":"e_1_3_1_5_2","article-title":"Recommendations in location-based social networks: A survey","volume":"19","author":"Bao Jie","year":"2015","unstructured":"Jie Bao, Yu Zheng, David Wilkie, and Mohamed F. Mokbel. 2015. Recommendations in location-based social networks: A survey. GeoInformatica 19, 3 (2015).","journal-title":"GeoInformatica"},{"key":"e_1_3_1_6_2","volume-title":"Process Control: Analysis, Design, Simulation","author":"Bequette B. Wayne","year":"2001","unstructured":"B. Wayne Bequette. 2001. Process Control: Analysis, Design, Simulation. Prentice Hall."},{"key":"e_1_3_1_7_2","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/j.knosys.2013.03.012","article-title":"Recommender systems survey","author":"Bobadilla J.","year":"2013","unstructured":"J. Bobadilla, F. Ortega, A. Hernando, and A. Guti\u00e9rrez. 2013. Recommender systems survey. Knowledge-Based Systems (2013), 109\u2013132.","journal-title":"Knowledge-Based Systems"},{"key":"e_1_3_1_8_2","volume-title":"VLDB","author":"Brakatsoulas Sotiris","year":"2005","unstructured":"Sotiris Brakatsoulas, Dieter Pfoser, Randall Salas, and Carola Wenk. 2005. On map-matching vehicle tracking data. In VLDB."},{"key":"e_1_3_1_9_2","first-page":"1340","volume-title":"29th IEEE International Conference on Data Engineering","author":"Cao Xin","year":"2013","unstructured":"Xin Cao, Lisi Chen, Gao Cong, Jihong Guan, Nhan-Tue Phan, and Xiaokui Xiao. 2013. KORS: Keyword-aware optimal route search system. In 29th IEEE International Conference on Data Engineering, Christian S. Jensen, Christopher M. Jermaine, and Xiaofang Zhou (Eds.). 1340\u20131343."},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350234"},{"key":"e_1_3_1_11_2","volume-title":"ACM SIGMOD","author":"Chen Lisi","year":"2013","unstructured":"Lisi Chen, Gao Cong, and Xin Cao. 2013. An efficient query indexing mechanism for filtering geo-textual data. In ACM SIGMOD. ACM."},{"key":"e_1_3_1_12_2","volume-title":"IEEE ICDE","author":"Chen Lisi","year":"2020","unstructured":"Lisi Chen, Shuo Shang, Christian S. Jensen, Bin Yao, and Panos Kalnis. 2020. Parallel semantic trajectory similarity join. In IEEE ICDE."},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00661-w"},{"key":"e_1_3_1_14_2","volume-title":"SSTD","author":"Costa Camila F.","year":"2017","unstructured":"Camila F. Costa and Mario A. Nascimento. 2017. Towards spatially- and category-wise k-diverse nearest neighbors queries. In SSTD."},{"key":"e_1_3_1_15_2","first-page":"656","volume-title":"Proceedings of the 24th International Conference on Data Engineering, ICDE","author":"Felipe Ian De","year":"2008","unstructured":"Ian De Felipe, Vagelis Hristidis, and Naphtali Rishe. 2008. Keyword search on spatial databases. In Proceedings of the 24th International Conference on Data Engineering, ICDE. 656\u2013665."},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/280277.280279"},{"key":"e_1_3_1_17_2","article-title":"A personalized point-of-interest recommendation model via fusion of geo-social information","volume":"273","author":"Gao Rong","year":"2018","unstructured":"Rong Gao, Jing Li, Xuefei Li, Chengfang Song, and Yifei Zhou. 2018. A personalized point-of-interest recommendation model via fusion of geo-social information. Neurocomputing 273 (2018).","journal-title":"Neurocomputing"},{"issue":"2","key":"e_1_3_1_18_2","article-title":"Algorithms for constrained k-nearest neighbor queries over moving object trajectories","volume":"14","author":"Gao Yunjun","year":"2010","unstructured":"Yunjun Gao, Baihua Zheng, Gencai Chen, and Qing Li. 2010. Algorithms for constrained k-nearest neighbor queries over moving object trajectories. GeoInformatica 14, 2 (2010).","journal-title":"GeoInformatica"},{"key":"e_1_3_1_19_2","volume-title":"WEA Workshop","author":"Geisberger Robert","year":"2008","unstructured":"Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling. 2008. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In WEA Workshop."},{"key":"e_1_3_1_20_2","volume-title":"IJCAI","author":"Han Peng","year":"2020","unstructured":"Peng Han, Zhongxiao Li, Yong Liu, Peilin Zhao, Jing Li, Hao Wang, and Shuo Shang. 2020. Contextualized point-of-interest recommendation. In IJCAI, Christian Bessiere (Ed.)."},{"key":"e_1_3_1_21_2","volume-title":"SOCS","author":"Harabor Daniel Damir","year":"2018","unstructured":"Daniel Damir Harabor and Peter James Stuckey. 2018. Forward search in contraction hierarchies. In SOCS."},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-018-0643-5"},{"key":"e_1_3_1_23_2","first-page":"894","volume-title":"Very Large Data Bases (VLDB)","author":"Hu Haibo","year":"2006","unstructured":"Haibo Hu, Dik Lun Lee, and Victor C. S. Lee. 2006. Distance indexing on road networks. In Very Large Data Bases (VLDB). 894\u2013905."},{"issue":"2","key":"e_1_3_1_24_2","article-title":"Location based services: Ongoing evolution and research agenda","volume":"12","author":"Huang Haosheng","year":"2018","unstructured":"Haosheng Huang, Georg Gartner, Jukka Matthias Krisp, Martin Raubal, and Nico Van de Weghe. 2018. Location based services: Ongoing evolution and research agenda. J. Locat. Based Serv. 12, 2 (2018).","journal-title":"J. Locat. Based Serv."},{"key":"e_1_3_1_25_2","volume-title":"IEEE MDM","author":"Issa Hamza","year":"2016","unstructured":"Hamza Issa and Maria Luisa Damiani. 2016. Efficient access to temporally overlaying spatial and textual trajectories. In IEEE MDM."},{"key":"e_1_3_1_26_2","volume-title":"Complexity of Computer Computations","author":"Karp Richard M.","year":"1972","unstructured":"Richard M. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations."},{"issue":"10","key":"e_1_3_1_27_2","article-title":"An experimental evaluation of point-of-interest recommendation in location-based social networks","volume":"10","author":"Liu Yiding","year":"2017","unstructured":"Yiding Liu, Tuan-Anh Pham, Gao Cong, and Quan Yuan. 2017. An experimental evaluation of point-of-interest recommendation in location-based social networks. Proc. VLDB Endow. 10, 10 (2017).","journal-title":"Proc. VLDB Endow."},{"key":"e_1_3_1_28_2","volume-title":"IEEE ICDE","author":"Liu Ziyi","year":"2021","unstructured":"Ziyi Liu, Lei Li, Mengxuan Zhang, Wen Hua, Pingfu Chao, and Xiaofang Zhou. 2021. Efficient constrained shortest path query answering with forest hop labeling. In IEEE ICDE."},{"key":"e_1_3_1_29_2","volume-title":"ACM SIGMOD","author":"Lu Jiaheng","year":"2011","unstructured":"Jiaheng Lu, Ying Lu, and Gao Cong. 2011. Reverse spatial and textual k nearest neighbor search. In ACM SIGMOD."},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551863"},{"key":"e_1_3_1_31_2","volume-title":"Location-Aware Technologies","author":"Miller Harvey J.","year":"2017","unstructured":"Harvey J. Miller. 2017. Location-Aware Technologies. Springer."},{"issue":"1","key":"e_1_3_1_32_2","article-title":"Mobility data science (Dagstuhl Seminar 22021)","volume":"12","author":"Mokbel Mohamed","year":"2022","unstructured":"Mohamed Mokbel, Mahmoud Sakr, Li Xiong, Andreas Z\u00fcfle, Jussara Almeida, Taylor Anderson, Walid Aref, Gennady Andrienko, Natalia Andrienko, Yang Cao, et\u00a0al. 2022. Mobility data science (Dagstuhl Seminar 22021). Dagstuhl Reports 12, 1 (2022).","journal-title":"Dagstuhl Reports"},{"key":"e_1_3_1_33_2","article-title":"Reverse nearest neighbor search in semantic trajectories for Location based Services","author":"Pan Xiao","year":"2020","unstructured":"Xiao Pan, Shili Nie, Haibo Hu, Philip Yu, and Jingfeng Guo. 2020. Reverse nearest neighbor search in semantic trajectories for Location based Services. IEEE Transactions on Services Computing (2020).","journal-title":"IEEE Transactions on Services Computing"},{"issue":"4","key":"e_1_3_1_34_2","article-title":"Semantic trajectories modeling and analysis","volume":"45","author":"Parent Christine","year":"2013","unstructured":"Christine Parent, Stefano Spaccapietra, Chiara Renso, Gennady Andrienko, Natalia Andrienko, Vania Bogorny, Maria Luisa Damiani, Aris Gkoulalas-Divanis, Jose Macedo, Nikos Pelekis, et\u00a0al. 2013. Semantic trajectories modeling and analysis. ACM (CSUR) 45, 4 (2013).","journal-title":"ACM (CSUR)"},{"key":"e_1_3_1_35_2","volume-title":"RCIS","author":"Pourbafrani Mahsa","year":"2021","unstructured":"Mahsa Pourbafrani, Shuai Jiao, and Wil M. P. van der Aalst. 2021. SIMPT: Process improvement using interactive simulation of time-aware process trees. In RCIS."},{"key":"e_1_3_1_36_2","volume-title":"SEA","author":"Rice Michael N.","year":"2012","unstructured":"Michael N. Rice and Vassilis J. Tsotras. 2012. Exact graph search algorithms for generalized traveling salesman path problems. In SEA."},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-019-00358-x"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/MDM48529.2020.00028"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3474717.3483985"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-022-07413-x"},{"key":"e_1_3_1_41_2","volume-title":"SSTD","author":"Teng Xu","year":"2019","unstructured":"Xu Teng, Jingchao Yang, Joon-Seok Kim, Goce Trajcevski, Andreas Z\u00fcfle, and Mario A. Nascimento. 2019. Fine-grained diversification of proximity constrained queries on road networks. In SSTD."},{"key":"e_1_3_1_42_2","volume-title":"ICDM","author":"Tong Hanghang","year":"2006","unstructured":"Hanghang Tong, Christos Faloutsos, and Jia-Yu Pan. 2006. Fast random walk with restart and its applications. In ICDM."},{"key":"e_1_3_1_43_2","article-title":"Geometric containers for efficient shortest-path computation","volume":"10","author":"Wagner Dorothea","year":"2005","unstructured":"Dorothea Wagner, Thomas Willhalm, and Christos Zaroliagis. 2005. Geometric containers for efficient shortest-path computation. Journal of Experimental Algorithmics (JEA) 10 (2005).","journal-title":"Journal of Experimental Algorithmics (JEA)"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00250"},{"key":"e_1_3_1_45_2","article-title":"Finding the shortest path with vertex constraint over large graphs","author":"Yang Yajun","year":"2019","unstructured":"Yajun Yang, Zhongfei Li, Xin Wang, and Qinghua Hu. 2019. Finding the shortest path with vertex constraint over large graphs. Complexity (2019).","journal-title":"Complexity"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.5555\/1128596.1128765"},{"key":"e_1_3_1_47_2","volume-title":"Proceedings of ACM CIKM","author":"Yuan Quan","year":"2014","unstructured":"Quan Yuan, Gao Cong, and Aixin Sun. 2014. Graph-based point-of-interest recommendation with geographical and temporal influences. In Proceedings of ACM CIKM."},{"key":"e_1_3_1_48_2","first-page":"54","volume-title":"23rd IEEE International Conference on Mobile Data Management, MDM 2022, Paphos, Cyprus, June 6-9, 2022","author":"Zang Andi","year":"2022","unstructured":"Andi Zang, Xiaofeng Zhu, Ce Li, Fan Zhou, and Goce Trajcevski. 2022. Integrating heterogeneous sources for learned prediction of vehicular data consumption. In 23rd IEEE International Conference on Mobile Data Management, MDM 2022, Paphos, Cyprus, June 6-9, 2022. IEEE, 54\u201363."},{"issue":"7","key":"e_1_3_1_49_2","article-title":"Inverted linear quadtree: Efficient top k spatial keyword search","volume":"28","author":"Zhang Chengyuan","year":"2016","unstructured":"Chengyuan Zhang, Ying Zhang, Wenjie Zhang, and Xuemin Lin. 2016. Inverted linear quadtree: Efficient top k spatial keyword search. IEEE TKDE 28, 7 (2016).","journal-title":"IEEE TKDE"},{"key":"e_1_3_1_50_2","volume-title":"EDBT","author":"Zhang Chengyuan","year":"2014","unstructured":"Chengyuan Zhang, Ying Zhang, Wenjie Zhang, Xuemin Lin, Muhammad Aamir Cheema, and Xiaoyang Wang. 2014. Diversified spatial keyword search on road networks. In EDBT."},{"key":"e_1_3_1_51_2","article-title":"A survey of point-of-interest recommendation in location-based social networks","volume":"1607","author":"Zhao Shenglin","year":"2016","unstructured":"Shenglin Zhao, Irwin King, and Michael R. Lyu. 2016. A survey of point-of-interest recommendation in location-based social networks. CoRR abs\/1607.00647 (2016). http:\/\/arxiv.org\/abs\/1607.00647.","journal-title":"CoRR"},{"key":"e_1_3_1_52_2","volume-title":"IEEE ICDE","author":"Zheng Kai","year":"2013","unstructured":"Kai Zheng, Shuo Shang, Nicholas Jing Yuan, and Yi Yang. 2013. Towards efficient search for activity trajectories. In IEEE ICDE."},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2399306"},{"issue":"2","key":"e_1_3_1_54_2","article-title":"Semi-supervised trajectory understanding with POI attention for end-to-end trip recommendation","volume":"6","author":"Zhou Fan","year":"2020","unstructured":"Fan Zhou, Hantao Wu, Goce Trajcevski, Ashfaq A. Khokhar, and Kunpeng Zhang. 2020. Semi-supervised trajectory understanding with POI attention for end-to-end trip recommendation. ACM Trans. Spatial Algorithms Syst. 6, 2 (2020).","journal-title":"ACM Trans. Spatial Algorithms Syst."},{"key":"e_1_3_1_55_2","volume-title":"WWW","author":"Zhou Fan","year":"2019","unstructured":"Fan Zhou, Ruiyang Yin, Kunpeng Zhang, Goce Trajcevski, Ting Zhong, and Jin Wu. 2019. Adversarial point-of-interest recommendation. In WWW."}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3596601","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3596601","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:48:01Z","timestamp":1750178881000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3596601"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,23]]},"references-count":54,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9,30]]}},"alternative-id":["10.1145\/3596601"],"URL":"https:\/\/doi.org\/10.1145\/3596601","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2023,6,23]]},"assertion":[{"value":"2022-03-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-24","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}