AKILLI ŞEHİRLERDE BELİRLİ VERİ SETLERİ İÇİN MEKÂNSAL ARAMA ALGORİTMALARININ PERFORMANS KARŞILAŞTIRILMASI

Year 2020, Volume: 3 Issue: 1, 41 - 50, 30.08.2020

Mert Girgin , Ali Boyacı

Abstract

Dijitalleşen çağda akıllı şehir kavramı ortaya çıkmıştır. Akıllı şehirlerin temel amaçlarından biride zaman verimi sağlayacak bileşenler sunmaktır. Akıllı ulaşım ve otopark hizmetleri bu konsepte dahildir. Bu hizmetlerin temeli gerçek zamanlı uzamsal arama algoritmalarına dayanmaktadır. Gerçek zamanlı uzamsal aramalar için performanslı uzamsal arama algoritmaları kullanmamız gerekmektedir. Populer uzamsal arama algoritmaları; k en yakın komşu, dörtgen sorgular, r-ağacı ve kd-ağacıdır. Uzamsal düzlemin içerisinde yer alan bir noktadan yapılan sorguda doğru algoritmanın seçimi performans açısından önemlidir. Bu çalışmanın amacı; seçilen merkez noktası için küçük boyutlu sınırları belirli bir veri setindeki en yakın komşuyu en hızlı şekilde saptayan algoritmayı belirlemektir. Python dilinde yazılan 4 uzamsal arama algoritması yapılan testler ile karşılaştırılmış ve veri seti için en uygun algoritma belirlenmiştir. Tespit edilen algoritma veri setine benzer şehir bileşeni modelinde kullanılabilir bu sayede zamanın değerli olduğu şehir hayatında verimli zaman yönetimi sağlanmış olur.

Keywords

Akıllı Şehirler, Uzamsal Arama, k En Yakın Komşu, Dörtgen Sorgular, r-Ağacı ve kd-Ağacı

PERFORMANCE COMPARISON OF SPATIAL SEARCH ALGORTIHMS FOR SPECIFIC DATASETS IN SMART CITIES

Abstract

The concept of smart city has emerged in the digital age. One of the main purposes of smart cities is to provide components that will provide time efficiency. Smart transportation and parking services are included in this concept. The basis of these services is based on real-time spatial search algorithms. We need to use performance spatial search algorithms for real-time spatial searches. Popular spatial search algorithms; k nearest neighbor, rectangle queries, r-tree and kd-tree. In the query made from a point in the spatial plane, the selection of the correct algorithm is important in terms of performance. The purpose of this study; to determine the algorithm that determines the nearest neighbor in a given dataset in the fastest way for the selected center point. The 4 spatial search algorithms written in Python language were compared with the tests and the most suitable algorithm was determined for the data set. The algorithm can be used in the city component model similar to the data set, so efficient time management is provided in the city life where time is valuable.

Keywords

Smart Cities, Spatial Search, k Nearest Neighbor, Rectangle Queries, r-Tree and kd-Tree

References

• Cover, T., Hart, P. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13, 21-27.
• Digital in 2020. We are Social, https://wearesocial.com/digital-2020 Guttman, A. (1984). R Trees: A Dynamic Index Structure for Spatial Searching. Sigmod Record, 14, 47-57. Hou, W., Li, D., Xu, C., Zhang, H., Li, T. (2019). An Advanced k Nearest Neighbor Classification Algorithm Based on KD-tree. 2018 IEEE International Conference of Safety Produce Informatization (IICSPI), 10-12 Dec. 2018, Chongqing, China.
• Hu, L., Huang, M., Ke, S., Tsai, C. (2016). The distance function effect on k-nearest neighbor classification for medical datasets. SpringerPlus, 5, 1304.
• Li, G., Tang, J. (2010). A New K-NN Query Algorithm Based on the Traversal and Search of the Dynamic Rectangle. 2010 International Conference on E-Product E-Service and E-Entertainment, 7-9 Nov. 2010, Henan, China.
• Liu D, Lim E, Ng W. (2002). Efficient k nearest neighbor queries on remote spatial databases usingrange estimation. In: Proceedings of international conf. on scientific and statistical databasesmanagement (SSDMB), 2426 July 2002, pp 121–130, Edinburgh.
• Oliphant, T. E. (2007). Python for Scientific Computing. Computing in Science & Engineering, 9, 10-20. Zhang, S., Li, X., Zong, M., Zhu, X., Wang, R. (2017). Efficient kNN Classification With Different Numbers of Nearest Neighbors. IEEE Transactions on Neural Networks and Learning Systems, 29, 1774-1785.
• Zhang, Z., Zhang, J., Yang, J., Yang, Y. (2007). A New Approach to Creating Spatial Index with R-Tree. 2007 International Conference on Machine Learning and Cybernetics, 19-22 Aug. 2007, Hong Kong, China.
• Zhu, Q., Gong, J., Zhang, Y. (2007). An efficient 3D R-tree spatial index method for virtual geographic environments. ISPRS Journal of Photogrammetry and Remote Sensing, 62, 217-224.