{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T18:33:27Z","timestamp":1780598007325,"version":"3.54.1"},"reference-count":32,"publisher":"MDPI AG","issue":"19","license":[{"start":{"date-parts":[[2022,10,9]],"date-time":"2022-10-09T00:00:00Z","timestamp":1665273600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Key R&amp;D Program of China","award":["2019YFB1405302"],"award-info":[{"award-number":["2019YFB1405302"]}]},{"name":"National Key R&amp;D Program of China","award":["2016YFC1401900"],"award-info":[{"award-number":["2016YFC1401900"]}]},{"name":"National Key R&amp;D Program of China","award":["61872072"],"award-info":[{"award-number":["61872072"]}]},{"name":"National Key R&amp;D Program of China","award":["61073063"],"award-info":[{"award-number":["61073063"]}]},{"name":"National Natural Science Foundation of China","award":["2019YFB1405302"],"award-info":[{"award-number":["2019YFB1405302"]}]},{"name":"National Natural Science Foundation of China","award":["2016YFC1401900"],"award-info":[{"award-number":["2016YFC1401900"]}]},{"name":"National Natural Science Foundation of China","award":["61872072"],"award-info":[{"award-number":["61872072"]}]},{"name":"National Natural Science Foundation of China","award":["61073063"],"award-info":[{"award-number":["61073063"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>As a popular spatial operation, the k-Nearest Neighbors (kNN) query is widely used in various spatial application systems. How to efficiently process a kNN query on spatial big data has always been an important research topic in the field of spatial data management. The centralized solutions are not suitable for spatial big data due to their poor scalability, while the existing distributed solutions are not efficient enough to meet the high real-time requirements of some spatial applications. Therefore, we introduce the Proportional Integral Derivative (PID) control technology into kNN query processing and propose a PID-based kNN query processing algorithm (PIDKNN) for spatial big data based on Spark. In this algorithm, the whole data space is divided into grid cells of the same size using the grid partition method, and the grid-based index is constructed. On this basis, the grid-based density peak clustering algorithm is used to cluster spatial data, and the corresponding PID parameters are set for each cluster. When performing kNN queries, the PID algorithm is used to estimate the radius growth step size of kNN queries, thereby realizing kNN query processing with a variable query radius growth step based on a feedback mechanism, which greatly improves the efficiency of kNN query processing. A series of experimental results show that the PIDKNN algorithm has good performance and scalability and is superior to the existing parallel kNN query processing methods.<\/jats:p>","DOI":"10.3390\/s22197651","type":"journal-article","created":{"date-parts":[[2022,10,10]],"date-time":"2022-10-10T05:12:21Z","timestamp":1665378741000},"page":"7651","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A PID-Based kNN Query Processing Algorithm for Spatial Data"],"prefix":"10.3390","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1765-6597","authenticated-orcid":false,"given":"Baiyou","family":"Qiao","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ling","family":"Ma","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Linlin","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bing","family":"Hu","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2022,10,9]]},"reference":[{"key":"ref_1","unstructured":"Chi, Z., Li, F., and Jestes, J. (2012, January 27\u201330). Efficient Parallel kNN Joins for Large Data in MapReduce. Proceedings of the International Conference on Extending Database Technology, Berlin, Germany."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4018\/IJDST.2019100101","article-title":"Improving the Performance of kNN in the MapReduce Framework Using Locality Sensitive Hashing","volume":"10","author":"Bagui","year":"2019","journal-title":"Int. J. Distrib. Syst. Technol."},{"key":"ref_3","unstructured":"Dong, T. (2013). Research on Spatial Data Index and kNN Query Technology under Big Data. [M.D. Thesis, Dalian University of Technology]."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Yu, J., Wu, J., and Sarwat, M. (2015, January 3\u20136). Geospark: A Cluster Computing Framework for Processing Large-Scale Spatial Data. Proceedings of the SIGSPATIAL International Conference on Advances in Geographic Information Systems, Seattle, WA, USA.","DOI":"10.1145\/2820783.2820860"},{"key":"ref_5","unstructured":"Armbrust, M. (June, January 31). Spark sql: Relational Data Processing in Spark. Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD), Melbourne, Australia."},{"key":"ref_6","unstructured":"Xie, D., Li, F., and Yao, B. (November, January 31). Simba: Spatial in-memory Big Data Analysis. Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Burlingame, CA, USA."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"35","DOI":"10.5334\/dsj-2020-035","article-title":"SparkNN: A Distributed In-Memory Data Partitioning for KNN Queries on Big Spatial Data","volume":"19","author":"Ismail","year":"2020","journal-title":"Data Sci. J."},{"key":"ref_8","first-page":"863","article-title":"CircularTrip: An Effective Algorithm for Continuous kNN Queries","volume":"Volume 4443","author":"Cheema","year":"2007","journal-title":"Advances in Databases: Concepts, Systems and Applications, DASFAA 2007, Lecture Notes in Computer Science"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1554","DOI":"10.1109\/TKDE.2019.2942585","article-title":"GLAD: A Grid and Labeling Framework with Scheduling for Conflict-Aware kNN Queries","volume":"33","author":"He","year":"2021","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_10","first-page":"2278","article-title":"A kNN Query Processing Method for Spatio-Temporal Information","volume":"27","author":"Li","year":"2016","journal-title":"Acta Softw. Sin."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Kouiroukidis, N., and Evangelidis, G. (October, January 30). The Effects of Dimensionality Curse in High Dimensional kNN Search. Proceedings of the 2011 15th Panhellenic Conference on Informatics (PCI), Kastoria, Greece.","DOI":"10.1109\/PCI.2011.45"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1053","DOI":"10.1109\/TKDE.2020.2992594","article-title":"BrePartition: Optimized High-Dimensional kNN Search with Bregman Distances","volume":"34","author":"Song","year":"2022","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"876","DOI":"10.1016\/j.ins.2021.10.027","article-title":"HCTree+: A Workload-Guided Index for Approximate kNN Search","volume":"581","author":"Li","year":"2021","journal-title":"Inf. Sci."},{"key":"ref_14","unstructured":"Kolahdouzan, M., and Shahabi, C. (September, January 31). Voronoi-Based k Nearest Neighbor Search for Spatial Network Databases. Proceedings of the Thirtieth International Conference on Very Large Data Bases, VLDB Endowment, Toronto, ON, Canada."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"120997","DOI":"10.1109\/ACCESS.2019.2937667","article-title":"Gridvoronoi: An Efficient Spatial Index for Nearest Neighbor Query Processing","volume":"7","author":"Zhang","year":"2019","journal-title":"IEEE Access"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Yu, Z., and Jiao, K. (2017, January 25\u201327). Incremental Processing of Continuous k Nearest Neighbor Queries Over Moving Objects. Proceedings of the 2017 International Conference on Computer Systems, Electronics and, Control (ICCSEC), Dalian, China.","DOI":"10.1109\/ICCSEC.2017.8447050"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"3045","DOI":"10.1007\/s11227-021-03975-2","article-title":"R Hern\u00e1ndez-Garc\u00eda; et al. Fast kNN Query Processing over a Multi-Node GPU Environment","volume":"78","author":"Barrientos","year":"2021","journal-title":"J. Supercomput."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"4611","DOI":"10.1007\/s11227-017-2110-y","article-title":"Gpu-Based Exhaustive Algorithms Processing kNN Queries","volume":"73","author":"Barrientos","year":"2017","journal-title":"J. Supercomput."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1111\/cgf.14177","article-title":"Optimizing LBVH-Construction and Hierarchy-Traversal to accelerate kNN Queries on Point Clouds using the GPU","volume":"40","author":"Jakob","year":"2020","journal-title":"Comput. Graph. Forum"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1774","DOI":"10.1360\/crad20071020","article-title":"pgi-distance: An Efficient Parallel KNN-Join Processing Method","volume":"44","author":"He","year":"2007","journal-title":"Comput. Res. Dev."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Bareche, I., and Xia, Y. (2019). Selective Velocity Distributed Indexing for Continuously Moving Objects Model. ICA3PP 2019. Lecture Notes in Computer Science, Springer.","DOI":"10.1007\/978-3-030-38961-1_30"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"5539","DOI":"10.1007\/s00500-018-3548-4","article-title":"An Efficient Index Structure for Distributed k-Nearest Neighbours Query Processing","volume":"24","author":"Yang","year":"2020","journal-title":"Soft Comput."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Jang, M., Shin, Y.S., and Chang, J.W. (2015, January 24\u201326). A Grid-Based k-Nearest Neighbor Join for Large Scale Datasets on MapReduce. Proceedings of the IEEE 17th International Conference on High Performance Computing and Communications, New York, NY, USA.","DOI":"10.1109\/HPCC-CSS-ICESS.2015.189"},{"key":"ref_24","first-page":"96","article-title":"Research on Spatial Range Query Index Based on Spark","volume":"35","author":"Chen","year":"2018","journal-title":"Comput. Appl. Softw."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/s10115-020-01518-4","article-title":"BestNeighbor: Efficient Evaluation of kNN Queries on Large Time Series Databases","volume":"63","author":"Levchenko","year":"2021","journal-title":"Knowl. Inf. Syst."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Moutafis, P., Mavrommatis, G., Vassilakopoulos, M., and Corral, A. (2021). Efficient Group K Nearest-Neighbor Spatial Query Processing in Apache Spark. ISPRS Int. J. Geo-Inf., 10.","DOI":"10.3390\/ijgi10110763"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"30","DOI":"10.3389\/fdata.2020.00030","article-title":"LocationSpark: In-memory Distributed Spatial Query Processing and Optimization","volume":"3","author":"Tang","year":"2020","journal-title":"Front. Big Data"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Baig, F., Vo, H., Kur\u00e7, T.M., Saltz, J.H., and Wang, F. (2017, January 7\u201310). SparkGIS: Resource Aware Efficient In-Memory Spatial Query Processing. Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Redondo Beach, CA, USA.","DOI":"10.1145\/3139958.3140019"},{"key":"ref_29","unstructured":"Kambiz, T., Panda, R., and Tehrani, K.A. (2012). Introduction to PID Controllers\u2014Theory, Tuning and Application to Frontier Areas (Chapter 9\u2014PID Control Theory), BoD\u2013Books on Demand."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"160","DOI":"10.6113\/JPE.2015.15.1.160","article-title":"Optimum Design of Integer and Fractional-Order PID Controllers for Boost Converter Using SPEA Look-up Tables","volume":"15","author":"Amirahmadi","year":"2015","journal-title":"J. Power Electron."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"124828","DOI":"10.1109\/ACCESS.2019.2937978","article-title":"Fractional-Order PID Motion Control for AUV Using Cloud-Model-Based Quantum Genetic Algorithm","volume":"7","author":"Wan","year":"2019","journal-title":"IEEE Access"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Shalaby, R., El-Hossainy, M., and Abo-Zalam, B. (2022). Optimal Fractional-Order PID Controller Based on Fractional-Order Actor-Critic Algorithm. Neural Comput. Appl.","DOI":"10.1007\/s00521-022-07710-7"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/22\/19\/7651\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:48:35Z","timestamp":1760143715000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/22\/19\/7651"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,9]]},"references-count":32,"journal-issue":{"issue":"19","published-online":{"date-parts":[[2022,10]]}},"alternative-id":["s22197651"],"URL":"https:\/\/doi.org\/10.3390\/s22197651","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,9]]}}}