{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T04:26:29Z","timestamp":1777695989899,"version":"3.51.4"},"reference-count":22,"publisher":"SAGE Publications","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IDA"],"published-print":{"date-parts":[[2021,3,4]]},"abstract":"<jats:p>With the application of big data, various queries arise for information retrieval. Spatial group keyword queries aim to find a set of spatial objects that cover the query keywords and minimize a goal function such as the total distance between the objects and the query point. This problem is widely found in database applications and is known to be NP-hard. Efficient algorithms for solving this problem can only provide approximate solutions, and most of these algorithms achieve a fixed approximation ratio (the upper bound of the ratio of an approximate goal value to the optimal goal value). Thus, to obtain a self-adjusting algorithm, we propose an approximation algorithm for achieving a parametric approximation ratio. The algorithm makes a trade-off between the approximation ratio and time consumption enabling the users to assign arbitrary query accuracy. Additionally, it runs in an on-the-fly manner, making it scalable to large-scale applications. The efficiency and scalability of the algorithm were further validated using benchmark datasets.<\/jats:p>","DOI":"10.3233\/ida-195071","type":"journal-article","created":{"date-parts":[[2021,3,9]],"date-time":"2021-03-09T12:40:49Z","timestamp":1615293649000},"page":"305-319","source":"Crossref","is-referenced-by-count":9,"title":["A parametric approximation algorithm for spatial group keyword queries"],"prefix":"10.1177","volume":"25","author":[{"given":"Jincao","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ming","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","reference":[{"issue":"2","key":"10.3233\/IDA-195071_ref1","doi-asserted-by":"crossref","first-page":"333","DOI":"10.3233\/IDA-173752","article-title":"A framework for generating condensed co-location sets from spatial databases","volume":"23","author":"Yoo","year":"2019","journal-title":"Intelligent Data Analysis"},{"issue":"11","key":"10.3233\/IDA-195071_ref2","doi-asserted-by":"crossref","first-page":"1414","DOI":"10.14778\/3342263.3342277","article-title":"Finding attribute-aware similar regions for data analysis","volume":"12","author":"Feng","year":"2019","journal-title":"Proceedings of the VLDB Endowment"},{"issue":"6","key":"10.3233\/IDA-195071_ref3","doi-asserted-by":"crossref","first-page":"1546","DOI":"10.1109\/TKDE.2016.2520473","article-title":"Practical approximate k nearest neighbor queries with location and query privacy","volume":"28","author":"Yi","year":"2016","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"10.3233\/IDA-195071_ref4","doi-asserted-by":"crossref","unstructured":"I.D. Felipe, V. Hristidis and N. Rishe, Keyword search on spatial databases, in: IEEE 24th International Conference on Data Engineering, 2008, pp. 656\u2013665.","DOI":"10.1109\/ICDE.2008.4497474"},{"key":"10.3233\/IDA-195071_ref5","doi-asserted-by":"crossref","unstructured":"D. Zhang, Y.M. Chee, A. Mondal, A.K.H. Tung and M. Kitsuregawa, Keyword search in spatial databases: Towards searching by document, in: IEEE 25th International Conference on Data Engineering, 2009, pp. 688\u2013699.","DOI":"10.1109\/ICDE.2009.77"},{"key":"10.3233\/IDA-195071_ref6","doi-asserted-by":"crossref","unstructured":"X. Cao, G. Cong, C.S. Jensen and B.C. Ooi, Collective spatial keyword querying, in: SIGMOD\u201911, 2011, pp. 373\u2013384.","DOI":"10.1145\/1989323.1989363"},{"key":"10.3233\/IDA-195071_ref8","doi-asserted-by":"crossref","unstructured":"C. Long, R.C.-W. Wong, K. Wang and A.W.-C. Fu, Collective spatial keyword queries: A distance owner-driven approach, in: SIGMOD\u201913, 2013, pp. 689\u2013700.","DOI":"10.1145\/2463676.2465275"},{"issue":"4","key":"10.3233\/IDA-195071_ref9","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1007\/s00778-015-0388-z","article-title":"Finding top-k relevant groups of spatial web objects","volume":"24","author":"Skovsgaard","year":"2015","journal-title":"The VLDB Journal"},{"issue":"9","key":"10.3233\/IDA-195071_ref10","doi-asserted-by":"crossref","first-page":"1712","DOI":"10.1109\/TKDE.2018.2800746","article-title":"On generalizing collective spatial keyword queries","volume":"30","author":"Chan","year":"2018","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"10.3233\/IDA-195071_ref11","doi-asserted-by":"crossref","unstructured":"A.R. Mahmood, W.G. Aref, A.M. Aly and M. Tang, Atlas: On the expression of spatial-keyword group queries using extended relational constructs, in: Proceedings of the 24th ACM SIGSPATIAL\/GIS, 45, 2016, pp. 1\u201310.","DOI":"10.1145\/2996913.2996987"},{"issue":"2","key":"10.3233\/IDA-195071_ref12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2772600","article-title":"Efficient processing of spatial group keyword queries","volume":"40","author":"Cao","year":"2015","journal-title":"ACM Transactions on Database Systems"},{"key":"10.3233\/IDA-195071_ref13","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/j.jcss.2017.09.009","article-title":"Time-approximation trade-offs for inapproximable problems","volume":"92","author":"Bonnet","year":"2018","journal-title":"Journal of Computer and System Sciences"},{"issue":"16","key":"10.3233\/IDA-195071_ref14","doi-asserted-by":"crossref","first-page":"957","DOI":"10.1016\/j.ipl.2009.05.003","article-title":"Exponential-time approximation of weighted set cover","volume":"109","author":"Cygan","year":"2009","journal-title":"Information Processing Letters"},{"issue":"21\u201323","key":"10.3233\/IDA-195071_ref15","doi-asserted-by":"crossref","first-page":"2184","DOI":"10.1016\/j.tcs.2009.02.007","article-title":"Efficient approximation of min set cover by moderately exponential algorithms","volume":"410","author":"Bourgeois","year":"2009","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"10.3233\/IDA-195071_ref16","doi-asserted-by":"crossref","first-page":"337","DOI":"10.14778\/1687627.1687666","article-title":"Efficient retrieval of the top-k most relevant spatial web objects","volume":"2","author":"Cong","year":"2009","journal-title":"Proceedings of the VLDB Endowment"},{"key":"10.3233\/IDA-195071_ref17","doi-asserted-by":"crossref","unstructured":"A. Guttman, R-trees: A dynamic index structure for spatial searching, in: SIGMOD\u201984, 1984, pp. 47\u201357.","DOI":"10.1145\/971697.602266"},{"key":"10.3233\/IDA-195071_ref18","doi-asserted-by":"crossref","unstructured":"N. Roussopoulos, S. Kelley and F. Vincent, Nearest neighbor queries, in: SIGMOD\u201995, 1995, pp. 71\u201379.","DOI":"10.1145\/568271.223794"},{"key":"10.3233\/IDA-195071_ref19","doi-asserted-by":"crossref","unstructured":"R. Bayer and E.M. McCreight, Organization and maintenance of large ordered indexes, in: ACM SIGFIDET Workshop on Data Description and Access, 1970, pp. 107\u2013141.","DOI":"10.21236\/AD0712079"},{"issue":"4","key":"10.3233\/IDA-195071_ref20","doi-asserted-by":"crossref","first-page":"878","DOI":"10.1109\/TKDE.2013.66","article-title":"Fast nearest neighbor search with keywords","volume":"26","author":"Tao","year":"2014","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"issue":"2","key":"10.3233\/IDA-195071_ref21","doi-asserted-by":"crossref","first-page":"243","DOI":"10.3233\/IDA-150418","article-title":"Cd-tree: A clustering-based dynamic indexing and retrieval approach","volume":"21","author":"Wan","year":"2017","journal-title":"Intelligent Data Analysis"},{"key":"10.3233\/IDA-195071_ref22","doi-asserted-by":"crossref","unstructured":"A. Almaslukh and A. Magdy, Evaluating spatial-keyword queries on streaming data, in: Proceedings of the 26th ACM SIGSPATIAL\/GIS, 2018, pp. 209\u2013218.","DOI":"10.1145\/3274895.3274936"},{"issue":"105","key":"10.3233\/IDA-195071_ref24","first-page":"1","article-title":"A note on set cover inapproximability independent of universe size","volume":"14","author":"Nelson","year":"2007","journal-title":"Electronic Colloquium on Computational Complexity"}],"container-title":["Intelligent Data Analysis"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/IDA-195071","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T09:18:59Z","timestamp":1777454339000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/IDA-195071"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,4]]},"references-count":22,"journal-issue":{"issue":"2"},"URL":"https:\/\/doi.org\/10.3233\/ida-195071","relation":{},"ISSN":["1088-467X","1571-4128"],"issn-type":[{"value":"1088-467X","type":"print"},{"value":"1571-4128","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,4]]}}}