Open AccessTesting Performance (Time Analysis) of Nearest Neighbour (NN) Search Algorithms on K-d Trees
Author(s) -
Mihir Goyenka,
Ayush Kedia
Publication year - 2021
Publication title -
international journal of advanced trends in computer science and engineering
Language(s) - English
Resource type - Journals
ISSN - 2278-3091
DOI - 10.30534/ijatcse/2021/041052021
Subject(s) - binary search tree , ternary search tree , tree (set theory) , optimal binary search tree , search algorithm , computer science , k d tree , time complexity , curse of dimensionality , algorithm , dimension (graph theory) , binary search algorithm , search tree , iterative deepening depth first search , weight balanced tree , mathematics , binary tree , best first search , combinatorics , tree traversal , beam search , interval tree , artificial intelligence
K-d tree (k-dimensional tree) is a space partitioning data structure for organizing points in a k-dimensional space. K-d tree, or Multidimensional Binary Search Tree is a useful data structure for several applications such as searches involving a multidimensional search key (e.g., Range Search and Nearest Neighbour Search). K-d trees are a special case of binary space partitioning trees.KNN Search is a searching algorithm with complexity O(N log N) {N= no. of data points}. This search algorithm is relatively better than brute force search {Complexity= O(n*k); where k=No. of neighbours searched, N=No. of Data Points in Kd tree} for dimensions N>>2D {N=No. of Points, D=Dimensionality of Tree}.Furthermore, Parallel KNN Search is much more efficient and performs better than KNN Search, as it harnesses parallel processing capabilities of computers and thus, results in better search time.This paper tests the time performance of KNN Search and Parallel KNN Search and compares them by plotting it on a 3D graph. A more comprehensive comparison is done by use of 2D graphs for each dimension(from 2 to 20).