{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T04:39:06Z","timestamp":1769315946229,"version":"3.49.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,2,3]],"date-time":"2022-02-03T00:00:00Z","timestamp":1643846400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,3]],"date-time":"2022-02-03T00:00:00Z","timestamp":1643846400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61902438, 61902439, U1811264, U19112031"],"award-info":[{"award-number":["61902438, 61902439, U1811264, U19112031"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Sci. Eng."],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The optimal sequenced route (OSR) query, as a popular problem in route planning for smart cities, searches for a minimum-distance route passing through several POIs in a specific order from a starting position. In reality, POIs are usually rated, which helps users in making decisions. Existing OSR queries neglect the fact that the POIs in the same category could have different scores, which may affect users\u2019 route choices. In this paper, we study a novel variant of OSR query, namely <jats:italic>Rating Constrained Optimal Sequenced Route query (RCOSR)<\/jats:italic>, in which the rating score of each POI in the optimal sequenced route should exceed the query threshold. To efficiently process RCOSR queries, we first extend the existing TD-OSR algorithm to propose a baseline method, called <jats:italic>MTDOSR<\/jats:italic>. To tackle the shortcomings of MTDOSR, we try to design a new RCOSR algorithm, namely <jats:italic>Optimal Subroute Expansion (OSE) Algorithm<\/jats:italic>. To enhance the OSE algorithm, we propose a <jats:italic>Reference Node Inverted Index (RNII)<\/jats:italic> to accelerate the distance computation of POI pairs in OSE and quickly retrieve the POIs of each category. To make full use of the OSE and RNII, we further propose a new efficient RCOSR algorithm, called <jats:italic>Recurrent Optimal Subroute Expansion (ROSE)<\/jats:italic>, which recurrently utilizes OSE to compute the current optimal route as the guiding path and update the distance of POI pairs to guide the expansion. Then, we extend our techniques to handle a variation of RCOSR query, namely RC<jats:italic>k<\/jats:italic>OSR query. The experimental results demonstrate that the proposed algorithm significantly outperforms the existing approaches.<\/jats:p>","DOI":"10.1007\/s41019-022-00177-5","type":"journal-article","created":{"date-parts":[[2022,2,3]],"date-time":"2022-02-03T17:04:56Z","timestamp":1643907896000},"page":"3-15","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Top k Optimal Sequenced Route Query with POI Preferences"],"prefix":"10.1007","volume":"7","author":[{"given":"Huaijie","family":"Zhu","sequence":"first","affiliation":[]},{"given":"Wenbin","family":"Li","sequence":"additional","affiliation":[]},{"given":"Wei","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Jian","family":"Yin","sequence":"additional","affiliation":[]},{"given":"Jianliang","family":"Xu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,3]]},"reference":[{"key":"177_CR1","doi-asserted-by":"crossref","unstructured":"Ahmadi E, Nascimento MA (2015) A mixed breadth-depth first search strategy for sequenced group trip planning queries. In: MDM. pp 24\u201333","DOI":"10.1109\/MDM.2015.49"},{"issue":"2","key":"177_CR2","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/s00530-012-0286-9","volume":"19","author":"H Al-Khalidi","year":"2013","unstructured":"Al-Khalidi H, Abbas Z, Safar M (2013) Approximate range query processing in spatial network databases. Multimed Syst 19(2):151\u2013161","journal-title":"Multimed Syst"},{"key":"177_CR3","doi-asserted-by":"crossref","unstructured":"Barua S, Jahan R, Ahmed T (2017) Weighted optimal sequenced group trip planning queries. In: MDM, pp 222\u2013227","DOI":"10.1109\/MDM.2017.37"},{"key":"177_CR4","doi-asserted-by":"crossref","unstructured":"Chen H, Ku W, Sun M, Zimmermann R (2008) The multi-rule partial sequenced route query. In: SIGSPATIAL, pp 1\u201310","DOI":"10.1145\/1463434.1463448"},{"key":"177_CR5","doi-asserted-by":"crossref","unstructured":"Chen B, Zhu H, Liu W, Yin J, Xu J (2021) Querying optimal routes for group meetup. Data Sci Eng (11)","DOI":"10.1007\/s41019-021-00153-5"},{"key":"177_CR6","doi-asserted-by":"crossref","unstructured":"Costa CF, Nascimento MA, Mac\u00eado JA, Theodoridis Y, Pelekis N, Machado J (2015) Optimal time-dependent sequenced route queries in road networks. In: SIGSPATIAL, pp 1\u20134","DOI":"10.1145\/2820783.2820846"},{"issue":"4","key":"177_CR7","first-page":"679","volume":"19","author":"J Dai","year":"2016","unstructured":"Dai J, Liu C, Xu J, Ding Z (2016) On personalized and sequenced route planning. WWWJ 19(4):679\u2013705","journal-title":"WWWJ"},{"key":"177_CR8","doi-asserted-by":"crossref","unstructured":"Guttman A (1984) R-trees: a dynamic index structure for spatial searching. In: SIGMOD, pp 47\u201357","DOI":"10.1145\/971697.602266"},{"key":"177_CR9","doi-asserted-by":"crossref","unstructured":"Hashem T, Hashem T, Ali ME, Kulik L (2013) Group trip planning queries in spatial databases. In: SSTD, pp 259\u2013276","DOI":"10.1007\/978-3-642-40235-7_15"},{"key":"177_CR10","doi-asserted-by":"crossref","unstructured":"Hashem T, Barua S, Ali ME, Kulik L, Tanin E (2015) Efficient computation of trips with friends and families. In: CIKM, pp 931\u2013940","DOI":"10.1145\/2806416.2806433"},{"key":"177_CR11","unstructured":"Jahan R, Hashem T, Barua S (2017) Group trip scheduling (GTS) queries in spatial databases. In: EDBT, pp 390\u2013401"},{"key":"177_CR12","doi-asserted-by":"crossref","unstructured":"Kriegel H, Kr\u00f6ger P, Kunath P, Renz M, Schmidt T (2007) Proximity queries in large traffic networks. In: GIS, pp\u00a01\u20138","DOI":"10.1145\/1341012.1341040"},{"key":"177_CR13","doi-asserted-by":"crossref","unstructured":"Li F, Cheng D, Hadjieleftheriou M, Kollios G, Teng S (2005) On trip planning queries in spatial databases. In: SSTD, pp 273\u2013290","DOI":"10.1007\/11535331_16"},{"issue":"5","key":"177_CR14","first-page":"1097","volume":"25","author":"J Li","year":"2013","unstructured":"Li J, Yang YD, Mamoulis N (2013) Optimal route queries with arbitrary order constraints. TKDE 25(5):1097\u20131110","journal-title":"TKDE"},{"key":"177_CR15","doi-asserted-by":"crossref","unstructured":"Li W, Zhu H, Liu W, Yin J, Xu, J (2021) Optimal Sequenced Route Query with POI Preferences. In: Database systems for advanced applications, 26th international conference, DASFAA 2021, Taipei, Taiwan, April 11\u201314, 2021, Proceedings, Part I","DOI":"10.1007\/978-3-030-73194-6_31"},{"key":"177_CR16","doi-asserted-by":"crossref","unstructured":"Liu H, Jin C, Yang B, Zhou A (2018) Finding top-k optimal sequenced routes. In: 2018 IEEE 34th international conference on data engineering (ICDE)","DOI":"10.1109\/ICDE.2018.00058"},{"key":"177_CR17","doi-asserted-by":"crossref","unstructured":"Ohsawa Y, Htoo H, Sonehara N, Sakauchi M (2012) Sequenced route query in road network distance based on incremental euclidean restriction. In: DEXA, pp 484\u2013491","DOI":"10.1007\/978-3-642-32600-4_36"},{"key":"177_CR18","doi-asserted-by":"crossref","unstructured":"Ouyang D, Qin L, Chang L, Lin X, Zhang Y, Zhu Q (2018) When hierarchy meets 2-hop-labeling: efficient shortest distance queries on road networks. In: ICMD, pp 709\u2013724","DOI":"10.1145\/3183713.3196913"},{"key":"177_CR19","doi-asserted-by":"crossref","unstructured":"Samrose S, Hashem T, Barua S, Ali ME, Uddin MH, Mahmud MI (2015) Efficient computation of group optimal sequenced routes in road networks. In: MDM, pp 122\u2013127","DOI":"10.1109\/MDM.2015.68"},{"key":"177_CR20","first-page":"37","volume":"2018","author":"Y Sasaki","year":"2018","unstructured":"Sasaki Y, Ishikawa Y, Fujiwara Y, Onizuka M (2018) Sequenced route query with semantic hierarchy. EDBT 2018:37\u201348","journal-title":"EDBT"},{"issue":"4","key":"177_CR21","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/s10707-007-0034-z","volume":"12","author":"M Sharifzadeh","year":"2008","unstructured":"Sharifzadeh M, Shahabi C (2008) Processing optimal sequenced route queries using voronoi diagrams. GeoInformatica 12(4):411\u2013433","journal-title":"GeoInformatica"},{"issue":"4","key":"177_CR22","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1007\/s00778-006-0038-6","volume":"17","author":"M Sharifzadeh","year":"2008","unstructured":"Sharifzadeh M, Kolahdouzan MR, Shahabi C (2008) The optimal sequenced route query. VLDB J 17(4):765\u2013787","journal-title":"VLDB J"},{"issue":"4","key":"177_CR23","first-page":"35","volume":"24","author":"A Singhal","year":"2001","unstructured":"Singhal A (2001) Modern information retrieval: a brief overview. IEEE DEB 24(4):35\u201343","journal-title":"IEEE DEB"},{"key":"177_CR24","doi-asserted-by":"crossref","unstructured":"Yao B, Tang M, Li F (2011) Multi-approximate-keyword routing in gis data. In: SIGSPATIAL, pp 201\u2013210","DOI":"10.1145\/2093973.2094001"},{"key":"177_CR25","first-page":"602","volume":"04","author":"P Yawalkar","year":"2019","unstructured":"Yawalkar P, Ranu S (2019) Route recommendations on road networks for arbitrary user preference functions. 04:602\u2013613","journal-title":"Route recommendations on road networks for arbitrary user preference functions."},{"issue":"4","key":"177_CR26","first-page":"1846","volume":"12","author":"B Zheng","year":"2017","unstructured":"Zheng B, Su H, Hua W, Zheng K, Zhou X, Li G (2017) Efficient clue-based route search on road networks. TKDE 12(4):1846\u20131859","journal-title":"TKDE"},{"key":"177_CR27","doi-asserted-by":"crossref","unstructured":"Zhong R, Li G, Tan K, Zhou L(2013) G-tree: an efficient index for KNN search on road networks. In: CIKM, pp 39\u201348","DOI":"10.1145\/2505515.2505749"}],"container-title":["Data Science and Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-022-00177-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41019-022-00177-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-022-00177-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,2]],"date-time":"2022-03-02T07:34:38Z","timestamp":1646206478000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41019-022-00177-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,3]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["177"],"URL":"https:\/\/doi.org\/10.1007\/s41019-022-00177-5","relation":{},"ISSN":["2364-1185","2364-1541"],"issn-type":[{"value":"2364-1185","type":"print"},{"value":"2364-1541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,3]]},"assertion":[{"value":"3 June 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 September 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 January 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 February 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Yes.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}