Nearest Neighbour Search in k-dSLst Tree
Adv. Sci. Technol. Eng. Syst. J. 5(4), 160–166 (2020);
DOI: 10.25046/aj050419
In the last few years of research and innovations, lots of spatial data in the form of points, lines, polygons and circles have been made available. Traditional indexing methods are not perfect to store spatial data. To search for nearest neighbour is one of the challenges in different fields like spatiotemporal data mining, computer vision, traffic management and machine learning. Many novel data structures are proposed in the past, which use spatial partitioning and recursive breakdown of hyperplane to find the nearest neighbour efficiently. In this paper, we have adopted the same strategy and proposed a nearest neighbour search algorithm for k-dSLst tree. k-dSLst tree is based on k-d tree and sorted linked list to handle spatial data with duplicate keys, which is ignored by most of the spatial indexing structures based on k-d tree. The research work in this paper shows experimentally that where the time taken by brute force nearest neighbour search increases exponentially with increase in number of records with duplicate keys and size of dataset, the proposed algorithm k-dSLstNearestNeighbourSearch based on k-dSLst tree performs far better with approximately linear increase in search time.
- S. Shekhar et al., Spatiotemporal Data Mining: A Computational Perspective, International Journal of Geo-Information ISSN 2220-9964, 04, 2306-2338, 2015.
- S. Geetha, S. Velavan, “Optimization of Location Based Queries using Spatial Indexing, International Journal of Soft Computing, 4, 2014.
- Verma et al., “Comparison of Brute-Force and K-D Tree Algorithm, International Journal of Advanced Research in Computer and Communication Engineering, January, 03, 2014.
- A. Suhaibaha, et al., “3D Nearest Neighbour Search Using a Clustered Hierarchical Tree, The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XXIII ISPRS Congress, XLI-B2, 2016.
- J. Jaemin, et al., “A progressive k-d tree for approximate k-nearest neighbors, IEEE Workshop on Data Systems for Interactive Analysis (DSIA), 2017.
- W. David, R. Rafael, “Parallel kd-Tree Construction on the GPU with an Adaptive Split and Sort Strategy, International Journal of Parallel Programming, 46, 1139–1156, 2018.
- Stoimen. Computer Algorithms: Brute Force String Matching. Stoemen’s web log. [Online] March 2012.
- M.W. Andrew, “Efficient Memory-based Learning for Robot Control. Technical Report No. 209, Ph. D Thesis, Computer Laboratory, University of Cambridge, 1991.