{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T12:18:02Z","timestamp":1767183482476,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,3,15]],"date-time":"2021-03-15T00:00:00Z","timestamp":1615766400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,15]],"date-time":"2021-03-15T00:00:00Z","timestamp":1615766400000},"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"],"award-info":[{"award-number":["61902438"]}],"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":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivated by location-based social networks which allow people to access location-based services as a group, we study a novel variant of <jats:italic>optimal sequenced route<\/jats:italic> (<jats:italic>OSR<\/jats:italic>) queries, optimal sequenced route for group meetup (OSR-G) queries. OSR-G query aims to find the optimal meeting POI (point of interest) such that the maximum users\u2019 route distance to the meeting POI is minimized after each user visits a number of POIs of specific categories (e.g., gas stations, restaurants, and shopping malls) in a particular order. To process OSR-G queries, we first propose an <jats:italic>OSR-Based<\/jats:italic> (<jats:italic>OSRB<\/jats:italic>) algorithm as our baseline, which examines every POI in the meeting category and utilizes existing OSR (called <jats:italic>E-OSR<\/jats:italic>) algorithm to compute the optimal route for each user to the meeting POI. To address the shortcomings (i.e., requiring to examine every POI in the meeting category) of <jats:italic>OSRB<\/jats:italic>, we propose an <jats:italic>upper bound based filtering<\/jats:italic> algorithm, called <jats:italic>circle filtering<\/jats:italic> (<jats:italic>CF<\/jats:italic>) algorithm, which exploits the circle property to filter the unpromising meeting POIs. In addition, we propose a <jats:italic>lower bound based pruning<\/jats:italic> (<jats:italic>LBP<\/jats:italic>) algorithm, namely <jats:italic>LBP-SP<\/jats:italic> which exploits a shortest path lower bound to prune the unqualified meeting POIs to reduce the search space. Furthermore, we develop an approximate algorithm, namely APS, to accelerate OSR-G queries with a good approximation ratio. Finally the experimental results show that both <jats:italic>CF<\/jats:italic> and <jats:italic>LBP-SP<\/jats:italic> outperform the <jats:italic>OSRB<\/jats:italic> algorithm and have high pruning rates. Moreover, the proposed approximate algorithm runs faster than the exact OSR-G algorithms and has a good approximation ratio.<\/jats:p>","DOI":"10.1007\/s41019-021-00153-5","type":"journal-article","created":{"date-parts":[[2021,3,15]],"date-time":"2021-03-15T11:03:14Z","timestamp":1615806194000},"page":"180-191","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Querying Optimal Routes for Group Meetup"],"prefix":"10.1007","volume":"6","author":[{"given":"Bo","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Huaijie","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jian","family":"Yin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wang-Chien","family":"Lee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianliang","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,15]]},"reference":[{"key":"153_CR1","unstructured":"http:\/\/users.diag.uniroma1.it\/challenge9\/"},{"key":"153_CR2","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"},{"key":"153_CR3","doi-asserted-by":"crossref","unstructured":"Ahmadi E, Nascimento MA (2018) Optimal meeting points for public transit users. In: MDM. pp 15\u201323","DOI":"10.1109\/MDM.2018.00017"},{"issue":"11","key":"153_CR4","first-page":"1136","volume":"5","author":"X Cao","year":"2012","unstructured":"Cao X, Chen L, Cong G, Xiao X (2012) Keyword-aware optimal route search. PVLDB 5(11):1136\u20131147","journal-title":"PVLDB"},{"key":"153_CR5","doi-asserted-by":"crossref","unstructured":"Chen H, Ku W, Sun M, Zimmermann R (2008) The multi-rule partial sequenced route query. In: ACM-GIS. p 10","DOI":"10.1145\/1463434.1463448"},{"issue":"3","key":"153_CR6","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1007\/s10707-010-0115-2","volume":"15","author":"H Chen","year":"2011","unstructured":"Chen H, Ku W, Sun M, Zimmermann R (2011) The partial sequenced route query with traveling rules in road networks. GeoInformatica 15(3):541\u2013569","journal-title":"GeoInformatica"},{"key":"153_CR7","doi-asserted-by":"crossref","unstructured":"Costa CF, Nascimento MA, de\u00a0Mac\u00eado JAF, Theodoridis Y, Pelekis N, Machado JC (2015) Optimal time-dependent sequenced route queries in road networks. In: SIGSPATIAL. pp 56:1\u201356:4","DOI":"10.1145\/2820783.2820846"},{"issue":"4","key":"153_CR8","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1007\/s11280-015-0352-2","volume":"19","author":"J Dai","year":"2016","unstructured":"Dai J, Liu C, Xu J, Ding Z (2016) On personalized and sequenced route planning. World Wide Web 19(4):679\u2013705","journal-title":"World Wide Web"},{"key":"153_CR9","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":"153_CR10","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":"153_CR11","unstructured":"Jahan R, Hashem T, Barua S (2017) Group trip scheduling (GTS) queries in spatial databases. In: EDBT. pp 390\u2013401"},{"key":"153_CR12","doi-asserted-by":"crossref","unstructured":"Lettich F, Nascimento MA, Anwar S (2020) Trade-off aware sequenced routing queries (or OSR queries when pois are not free). In: 21st IEEE International conference on mobile data management, MDM 2020, Versailles, France, June 30 - July 3, 2020. pp 59\u201368. IEEE","DOI":"10.1109\/MDM48529.2020.00027"},{"issue":"1","key":"153_CR13","first-page":"117","volume":"3","author":"R Levin","year":"2010","unstructured":"Levin R, Kanza Y, Safra E, Sagiv Y (2010) Interactive route search in the presence of order constraints. Proc. VLDB Endow. 3(1):117\u2013128","journal-title":"Proc. VLDB Endow."},{"key":"153_CR14","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":"153_CR15","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":"153_CR16","doi-asserted-by":"crossref","unstructured":"Li W, Zhu H, Liu W, Yin J, Xu J (2021) Optimal sequenced route query with poi preferences. In: Dasffa. p. Accepted","DOI":"10.1007\/978-3-030-73194-6_31"},{"key":"153_CR17","doi-asserted-by":"crossref","unstructured":"Liu H, Jin C, Yang B, Zhou A (2018) Finding top-k optimal sequenced routes. In: ICDE. pp 569\u2013580","DOI":"10.1109\/ICDE.2018.00058"},{"key":"153_CR18","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":"153_CR19","doi-asserted-by":"crossref","unstructured":"Papadias D, Zhang J, Mamoulis N, Tao Y (2003) Query processing in spatial network databases. In: VLDB. pp 802\u2013813","DOI":"10.1016\/B978-012722442-8\/50076-8"},{"key":"153_CR20","doi-asserted-by":"crossref","unstructured":"Rice MN, Tsotras VJ (2013) Engineering generalized shortest path queries. In: ICDE. pp 949\u2013960","DOI":"10.1109\/ICDE.2013.6544888"},{"key":"153_CR21","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":"153_CR22","unstructured":"Sasaki Y, Ishikawa Y, Fujiwara Y, Onizuka M (2018) Sequenced route query with semantic hierarchy. In: B\u00f6hlen, M.H., Pichler, R., May, N., Rahm, E., Wu, S., Hose, K. (eds.) Proceedings of the 21st international conference on extending database technology, EDBT 2018, Vienna, Austria, March 26-29, 2018. pp 37\u201348. OpenProceedings.org"},{"issue":"4","key":"153_CR23","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 17(4):765\u2013787","journal-title":"VLDB"},{"issue":"4","key":"153_CR24","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":"11","key":"153_CR25","first-page":"968","volume":"4","author":"D Yan","year":"2011","unstructured":"Yan D, Zhao Z, Ng W (2011) Efficient algorithms for finding optimal meeting point on road networks. PVLDB 4(11):968\u2013979","journal-title":"PVLDB"},{"issue":"2","key":"153_CR26","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s10115-013-0686-y","volume":"42","author":"D Yan","year":"2015","unstructured":"Yan D, Zhao Z, Ng W (2015) Efficient processing of optimal meeting point queries in euclidean space and road networks. Knowl Inf Syst 42(2):319\u2013351","journal-title":"Knowl Inf Syst"}],"container-title":["Data Science and Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-021-00153-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41019-021-00153-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-021-00153-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,22]],"date-time":"2021-05-22T11:08:34Z","timestamp":1621681714000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41019-021-00153-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,15]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["153"],"URL":"https:\/\/doi.org\/10.1007\/s41019-021-00153-5","relation":{},"ISSN":["2364-1185","2364-1541"],"issn-type":[{"type":"print","value":"2364-1185"},{"type":"electronic","value":"2364-1541"}],"subject":[],"published":{"date-parts":[[2021,3,15]]},"assertion":[{"value":"15 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 January 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 February 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}