{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T17:30:30Z","timestamp":1783791030950,"version":"3.55.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,6,14]],"date-time":"2016-06-14T00:00:00Z","timestamp":1465862400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"publisher","award":["MOST 103-2221-E-002-286- MY2, MOST 101-2628-E-001-003-MY3, MOST 103-2221- E-001-005-MY2"],"award-info":[{"award-number":["MOST 103-2221-E-002-286- MY2, MOST 101-2628-E-001-003-MY3, MOST 103-2221- E-001-005-MY2"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2016,7,27]]},"abstract":"<jats:p>\n            Spatial proximity is one of the most important factors for the quick deployment of the task groups in various time-sensitive missions. This article proposes a new spatial query,\n            <jats:italic>Spatio-Social Team Query (SSTQ)<\/jats:italic>\n            , that forms a strong task group by considering (1) the group\u2019s spatial distance (i.e., transportation time), (2) skills of the candidate group members, and (3) social rapport among the candidates. Efficient processing of SSTQ is very challenging, because the aforementioned spatial, skill, and social factors need to be carefully examined. In this article, therefore, we first formulate two subproblems of SSTQ, namely\n            <jats:italic>Hop-Constrained Team Problem (HCTP)<\/jats:italic>\n            and\n            <jats:italic>Connection-Oriented Team Query (COTQ)<\/jats:italic>\n            . HCTP is a decision problem that considers only social and skill dimensions. We prove that HCTP is NP-Complete. Moreover, based on the hardness of HCTP, we prove that SSTQ is NP-Hard and\n            <jats:italic>inapproximable within any factor<\/jats:italic>\n            . On the other hand, COTQ is a special case of SSTQ that relaxes the social constraint. We prove that COTQ is NP-Hard and propose an approximation algorithm for COTQ, namely\n            <jats:italic>COTprox<\/jats:italic>\n            . Furthermore, based on the observations on COTprox, we devise an approximation algorithm,\n            <jats:italic>SSTprox<\/jats:italic>\n            , with a guaranteed error bound for SSTQ. Finally, to efficiently obtain the optimal solution to SSTQ for small instances, we design two efficient algorithms,\n            <jats:italic>SpatialFirst<\/jats:italic>\n            and\n            <jats:italic>SkillFirst<\/jats:italic>\n            , with different scenarios in mind. These two algorithms incorporate various effective ordering and pruning techniques to reduce the search space for answering SSTQ. Experimental results on real datasets indicate that the proposed algorithms can efficiently answer SSTQ under various parameter settings.\n          <\/jats:p>","DOI":"10.1145\/2818714","type":"journal-article","created":{"date-parts":[[2016,6,14]],"date-time":"2016-06-14T12:29:28Z","timestamp":1465907368000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Spatial-Proximity Optimization for Rapid Task Group Deployment"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5765-6551","authenticated-orcid":false,"given":"Chih-Ya","family":"Shen","sequence":"first","affiliation":[{"name":"Academia Sinica, Taipei, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"De-Nian","family":"Yang","sequence":"additional","affiliation":[{"name":"Academia Sinica, Taipei, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wang-Chien","family":"Lee","sequence":"additional","affiliation":[{"name":"Pennsylvania State University, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ming-Syan","family":"Chen","sequence":"additional","affiliation":[{"name":"National Taiwan University, Taipei, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,6,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1871437.1871515"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187950"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536206.2536218"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920891"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989363"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687666"},{"key":"e_1_2_1_7_1","volume-title":"Introductino to Algorithms","author":"Cormen Thomas H."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1947725.1947768"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972825.15"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559906"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516378"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/320248.320255"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.90"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063718"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972832.65"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557074"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SocialCom.2010.12"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2014.06.001"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465275"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339690"},{"key":"e_1_2_1_23_1","volume-title":"R-Trees: Theory and Applications","author":"Manolopoulos Yannis"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1080\/00107510500052444"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/977401.978090"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488482"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287395"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767861"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339679"},{"key":"e_1_2_1_31_1","volume-title":"Geo-social group queries with minimum acquaintance constraint. CoRR abs\/1406.7367","author":"Zhu Qijun","year":"2014"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818714","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2818714","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:42:49Z","timestamp":1750225369000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818714"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,14]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,7,27]]}},"alternative-id":["10.1145\/2818714"],"URL":"https:\/\/doi.org\/10.1145\/2818714","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,14]]},"assertion":[{"value":"2014-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-06-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}