Nearest Neighbour Search in k-dSLst Tree

Abstract

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.

Cite this paper

@article{hooda2020nearest,
  title = {{Nearest Neighbour Search in k-dSLst Tree}},
  author = {Hooda, Meenakshi and Gill, Sumeet},
  journal = {Advances in Science Technology and Engineering Systems Journal},
  volume = {5},
  number = {4},
  pages = {160--166},
  year = {2020},
  doi = {10.25046/aj050419}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.

Related papers