{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T14:14:34Z","timestamp":1761401674981,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2013,4,1]],"date-time":"2013-04-01T00:00:00Z","timestamp":1364774400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["264994"],"award-info":[{"award-number":["264994"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee, Hong Kong","doi-asserted-by":"publisher","award":["HKBU210510, HKBU211512, and FRG2\/10-11\/106","PolyU 5302\/12E"],"award-info":[{"award-number":["HKBU210510, HKBU211512, and FRG2\/10-11\/106","PolyU 5302\/12E"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001747","name":"Hong Kong Baptist University","doi-asserted-by":"publisher","award":["HKBU210510, HKBU211512, and FRG2\/10-11\/106"],"award-info":[{"award-number":["HKBU210510, HKBU211512, and FRG2\/10-11\/106"]}],"id":[{"id":"10.13039\/501100001747","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2013,4]]},"abstract":"<jats:p>Web users and content are increasingly being geo-positioned. This development gives prominence to spatial keyword queries, which involve both the locations and textual descriptions of content. We study the efficient processing of continuously moving top-<jats:italic>k<\/jats:italic>spatial keyword (M<jats:italic>k<\/jats:italic>SK) queries over spatial text data. State-of-the-art solutions for moving queries employ<jats:italic>safe zones<\/jats:italic>that guarantee the validity of reported results as long as the user remains within the safe zone associated with a result. However, existing safe-zone methods focus solely on spatial locations and ignore text relevancy.<\/jats:p><jats:p>We propose two algorithms for computing safe zones that guarantee correct results at any time and that aim to optimize the server-side computation as well as the communication between the server and the client. We exploit tight and conservative approximations of safe zones and aggressive computational space pruning. We present techniques that aim to compute the next safe zone efficiently, and we present two types of conservative safe zones that aim to reduce the communication cost. Empirical studies with real data suggest that the proposals are efficient.<\/jats:p><jats:p>To understand the effectiveness of the proposed safe zones, we study analytically the expected area of a safe zone, which indicates on average for how long a safe zone remains valid, and we study the expected number of influence objects needed to define a safe zone, which gives an estimate of the average communication cost. The analytical modeling is validated through empirical studies.<\/jats:p>","DOI":"10.1145\/2445583.2445590","type":"journal-article","created":{"date-parts":[[2013,4,23]],"date-time":"2013-04-23T13:04:26Z","timestamp":1366722266000},"page":"1-47","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["Moving spatial keyword queries"],"prefix":"10.1145","volume":"38","author":[{"given":"Dingming","family":"Wu","sequence":"first","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong"}]},{"given":"Man Lung","family":"Yiu","sequence":"additional","affiliation":[{"name":"Hong Kong Polytechnic University, Hong Kong"}]},{"given":"Christian S.","family":"Jensen","sequence":"additional","affiliation":[{"name":"Aarhus University, Denmark"}]}],"member":"320","published-online":{"date-parts":[[2013,4,26]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(84)90064-5"},{"volume-title":"Proceedings of the International Database Engineering and Applications Symposium. 44--53","author":"Benetis R.","key":"e_1_2_2_2_1","unstructured":"Benetis , R. , Jensen , C. S. , Karciauskas , G. , and Saltenis , S . 2002. Nearest neighbor and reverse nearest neighbor queries for moving objects . In Proceedings of the International Database Engineering and Applications Symposium. 44--53 . Benetis, R., Jensen, C. S., Karciauskas, G., and Saltenis, S. 2002. Nearest neighbor and reverse nearest neighbor queries for moving objects. In Proceedings of the International Database Engineering and Applications Symposium. 44--53."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-005-0166-4"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015231126594"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34002-4_2"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920891"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989363"},{"volume-title":"Proceedings of the International Conference on Data Engineering. 189--200","author":"Cheema M. A.","key":"e_1_2_2_8_1","unstructured":"Cheema , M. A. , Brankovic , L. , Lin , X. , Zhang , W. , and Wang , W . 2010. Multi-guarded safe zone: An effective technique to monitor moving circular range queries . In Proceedings of the International Conference on Data Engineering. 189--200 . Cheema, M. A., Brankovic, L., Lin, X., Zhang, W., and Wang, W. 2010. Multi-guarded safe zone: An effective technique to monitor moving circular range queries. In Proceedings of the International Conference on Data Engineering. 189--200."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535569.2448955"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142505"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559907"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687666"},{"key":"e_1_2_2_13_1","volume-title":"Statististical Analysis of Spatial Point Patterns","author":"Diggle P. J.","unstructured":"Diggle , P. J. 2003. Statististical Analysis of Spatial Point Patterns 2 nd Ed. Arnold . Diggle, P. J. 2003. Statististical Analysis of Spatial Point Patterns 2nd Ed. Arnold.","edition":"2"},{"key":"e_1_2_2_14_1","volume-title":"Modern Geometry: The Straight Line and Circle","author":"Durell C. V.","year":"1961","unstructured":"Durell , C. V. 1961 . Modern Geometry: The Straight Line and Circle . Macmillan . Durell, C. V. 1961. Modern Geometry: The Straight Line and Circle. Macmillan."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311910"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497474"},{"key":"e_1_2_2_17_1","first-page":"85","article-title":"Geometric properties of market areas","volume":"20","author":"Gambini R.","year":"1968","unstructured":"Gambini , R. , Huff , D. L. , and Jenks , G. F. 1968 . Geometric properties of market areas . Regional Studies 20 , 1, 85 -- 92 . Gambini, R., Huff, D. L., and Jenks, G. F. 1968. Geometric properties of market areas. Regional Studies 20, 1, 85--92.","journal-title":"Regional Studies"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559906"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1080\/09595237300185321"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1138394.1138396"},{"volume-title":"Proceedings of the 30th International Conference on Very Large Data Bases. 840--851","author":"Kolahdouzan M. R.","key":"e_1_2_2_22_1","unstructured":"Kolahdouzan , M. R. and Shahabi , C . 2004. Voronoi-based k nearest neighbor search for spatial network databases . In Proceedings of the 30th International Conference on Very Large Data Bases. 840--851 . Kolahdouzan, M. R. and Shahabi, C. 2004. Voronoi-based k nearest neighbor search for spatial network databases. In Proceedings of the 30th International Conference on Very Large Data Bases. 840--851."},{"key":"e_1_2_2_23_1","article-title":"Spatial approximate string search","author":"Li F.","year":"2012","unstructured":"Li , F. , Yao , B. , Tang , M. , and Hadjieleftheriou , M. 2012 a. Spatial approximate string search . IEEE Trans. Knowl. Data Eng. Li, F., Yao, B., Tang, M., and Hadjieleftheriou, M. 2012a. Spatial approximate string search. IEEE Trans. Knowl. Data Eng.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.93"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.149"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989361"},{"key":"e_1_2_2_27_1","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1111\/j.0033-0124.2004.05602007.x","article-title":"Polygon characterization with the multiplicatively weighted Voronoi diagram","volume":"56","author":"Mu L.","year":"2004","unstructured":"Mu , L. 2004 . Polygon characterization with the multiplicatively weighted Voronoi diagram . Professional Geographer 56 , 2, 223 -- 239 . Mu, L. 2004. Polygon characterization with the multiplicatively weighted Voronoi diagram. Professional Geographer 56, 2, 223--239.","journal-title":"Professional Geographer"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453973"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470317013"},{"volume-title":"Introduction to Modern Information Retrieval","author":"Salton G.","key":"e_1_2_2_30_1","unstructured":"Salton , G. and McGill , M. J. 1986. Introduction to Modern Information Retrieval . McGraw-Hill . Salton, G. and McGill, M. J. 1986. Introduction to Modern Information Retrieval. McGraw-Hill."},{"volume-title":"Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases. 79--96","author":"Song Z.","key":"e_1_2_2_31_1","unstructured":"Song , Z. and Roussopoulos , N . 2001. K-nearest neighbor search for moving query point . In Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases. 79--96 . Song, Z. and Roussopoulos, N. 2001. K-nearest neighbor search for moving query point. In Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases. 79--96."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564730"},{"volume-title":"Proceedings of the 28th International Conference on Very Large Data Bases. 287--298","author":"Tao Y.","key":"e_1_2_2_33_1","unstructured":"Tao , Y. , Papadias , D. , and Shen , Q . 2002. Continuous nearest neighbor search . In Proceedings of the 28th International Conference on Very Large Data Bases. 287--298 . Tao, Y., Papadias, D., and Shen, Q. 2002. Continuous nearest neighbor search. In Proceedings of the 28th International Conference on Very Large Data Bases. 287--298."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0271-0"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767861"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.77"},{"volume-title":"Proceedings of the International Conference on Data Engineering. 521--532","author":"Zhang D.","key":"e_1_2_2_37_1","unstructured":"Zhang , D. , Ooi , B. C. , and Tung , A. K. H. 2010. Locating mapped resources in web 2.0 . In Proceedings of the International Conference on Data Engineering. 521--532 . Zhang, D., Ooi, B. C., and Tung, A. K. H. 2010. Locating mapped resources in web 2.0. In Proceedings of the International Conference on Data Engineering. 521--532."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872812"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1099554.1099584"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132956.1132959"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2445583.2445590","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2445583.2445590","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:34:09Z","timestamp":1750239249000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2445583.2445590"}},"subtitle":["Formulation, methods, and analysis"],"short-title":[],"issued":{"date-parts":[[2013,4]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["10.1145\/2445583.2445590"],"URL":"https:\/\/doi.org\/10.1145\/2445583.2445590","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2013,4]]},"assertion":[{"value":"2012-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-04-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}