{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:29:01Z","timestamp":1760243341287,"version":"build-2065373602"},"reference-count":19,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2014,10,23]],"date-time":"2014-10-23T00:00:00Z","timestamp":1414022400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Recently, developing efficient processing techniques in spatio-temporal databases has been a much discussed topic. Many applications, such as mobile information systems, traffic control system, and geographical information systems, can benefit from efficient processing of spatio-temporal queries. In this paper, we focus on processing an important type of spatio-temporal queries, the K-nearest neighbor (KNN) queries. Different from the previous research, the locations of objects are located by the sensors which are deployed in a grid-based manner. As the positioning technique used is not the GPS technique, but the sensor network technique, this results in a greater uncertainty regarding object location. With the uncertain location information of objects, we try to develop an efficient algorithm to process the KNN queries. Moreover, we design a probability model to quantify the possibility of each object being the query result. Finally, extensive experiments are conducted to demonstrate the efficiency of the proposed algorithms.<\/jats:p>","DOI":"10.3390\/a7040582","type":"journal-article","created":{"date-parts":[[2014,10,23]],"date-time":"2014-10-23T12:28:28Z","timestamp":1414067308000},"page":"582-596","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Processing KNN Queries in Grid-Based Sensor Networks"],"prefix":"10.3390","volume":"7","author":[{"given":"Yuan-Ko","family":"Huang","sequence":"first","affiliation":[{"name":"Department of Information Communication, Kao-Yuan University, No. 1821, Jhongshan Road,  Lujhu District, Kaohsiung City 82151, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2014,10,23]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Zhang, J., Zhu, M., Papadias, D., Tao, Y., and Lee, D.L. (2003, January 9\u201312). Location-based Spatial Queries. Proceedings of the 2003 ACM SIGMOD international conference on Management of data, San Diego, CA, USA.","DOI":"10.1145\/872757.872812"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Saltenis, S., Jensen, C.S., Leutenegger, S.T., and Lopez, M.A. (2000). Indexing the Positions of Continuously Moving Objects, ACM SIGMOD.","DOI":"10.1145\/342009.335427"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Kalashnikov, D.V., Prabhakar, S., Hambrusch, S., and Aref, W. (2002, January 2\u20136). Efficient evaluation of continuous range queries on moving objects. Proceedings of the International Conference on Database and Expert Systems Applications, Aix en, France.","DOI":"10.1007\/3-540-46146-9_72"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Tao, Y., and Papadias, D. (2002, January 3\u20136). Time Parameterized Queries in Spatio-Temporal Databases. Proceedings of the 2002 ACM SIGMOD international conference on Management of data, Madison, WI, USA.","DOI":"10.1145\/564691.564730"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Mokbel, M.F., Xiong, X., and Aref, W.G. (2004, January 13\u201318). Sina: Scalable Incremental Processing of Continuous Queries in Spatio-Temporal Databases. Proceedings of the 2004 ACM SIGMOD international conference on Management of data, Paris, France.","DOI":"10.1145\/1007568.1007638"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Mouratidis, K., Hadjieleftheriou, M., and Papadias, D. (2005, January 14\u201316). Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring. proceedings of the 2005 ACM SIGMOD international conference on Management of data, Baltimore, MD, USA.","DOI":"10.1145\/1066157.1066230"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"145","DOI":"10.3390\/a7010145","article-title":"The minimum scheduling time for convergecast in wireless sensor networks","volume":"7","author":"Jung","year":"2014","journal-title":"Algorithms"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"397","DOI":"10.3390\/a7030397","article-title":"Algorithm based on heuristic strategy to infer lossy links in wireless sensor networks","volume":"7","author":"Ma","year":"2014","journal-title":"Algorithms"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"121","DOI":"10.3390\/a2010121","article-title":"Probabilistic distributed algorithms for energy efficient routing and tracking in wireless sensor networks","volume":"2","author":"Nikoletseas","year":"2009","journal-title":"Algorithms"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1112","DOI":"10.1109\/TKDE.2004.46","article-title":"Querying Imprecise Data in Moving Object Environments","volume":"16","author":"Cheng","year":"2009","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_11","unstructured":"Sistla, A.P., Wolfson, O., Chamberlain, S., and Dao, S. (1997, January 7\u201311). Modeling and Querying Moving Objects. Proceedings of the International Conference on Data Engineering, Birmingham, UK."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Wolfson, O., Sistla, P., Xu, B., Zhou, J., Chamberlain, S., Yesha, T., and Rishe, N. (1999, January 5\u20137). Tracking Moving Objects Using Database Technology in DOMINO. Proceedings of the Fourth Workshop on Next Generation Information Technologies and Systems, Zikhron-Yaakov, Israel.","DOI":"10.1007\/3-540-48521-X_9"},{"key":"ref_13","unstructured":"Benetis, R., Jensen, C.S., Karciauskas, G., and Saltenis, S. (2002, January 17\u201319). Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects. Proceedings of the International Database Engineering and Applications Symposium, Edmonton, Canada."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1023\/A:1023403908170","article-title":"Fast Nearest-Neighbor Query Processing in Moving-Object Databases","volume":"7","author":"Raptopoulou","year":"2003","journal-title":"GeoInformatica"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Iwerks, G., Samet, H., and Smith, K. (2003, January 9\u201312). Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates. Proceedings of the International Conference on Very Large Data Bases, Berlin, Germany.","DOI":"10.1016\/B978-012722442-8\/50052-5"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Song, Z., and Roussopoulos, N. (2001, January 12\u201315). K-Nearest Neighbor Search for Moving Query Point. Proceedings of 7th International Symposium on Advances in Spatial and Temporal Databases, Redondo Beach, CA, USA.","DOI":"10.1007\/3-540-47724-1_5"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Nehme, R.V., and Rundensteiner, E.A. (2006, January 26\u201331). SCUBA: Scalable Cluster-Based Algorithm for Evaluating Continuous Spatio-Temporal Queries on Moving Objects. Proceedings of the 10th International Conference on Extending Database Technology, Munich, Germany.","DOI":"10.1007\/11687238_58"},{"key":"ref_18","unstructured":"Xiong, X., Mokbel, M.F., and Aref, W.G. (2005, January 5\u20138). SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatio-temporal Databases. Proceedings of the International Conference on Data Engineering, Tokyo, Japan."},{"key":"ref_19","unstructured":"Yu, X., Pu, K.Q., and Koudas, N. (2005, January 5\u20138). Monitoring K-Nearest Neighbor Queries Over Moving Objects. Proceedings of the International Conference on Data Engineering, Tokyo, Japan."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/7\/4\/582\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:17:22Z","timestamp":1760217442000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/7\/4\/582"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,23]]},"references-count":19,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2014,12]]}},"alternative-id":["a7040582"],"URL":"https:\/\/doi.org\/10.3390\/a7040582","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2014,10,23]]}}}