Comparison of Brute-Force and K-D Tree Algorithm

Abstract: Data mining may be viewed as the extraction of the hidden predictive information from large databases, is a powerful new technology with great potential to analyze important information in the data warehouse. Nearest neighbor search (NNS), also known as proximity search, similarity search or closest point search, is an optimization problem for finding closest points in metric spaces. Brute-force search is a very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement. A Brute-force algorithm for string matching problem has two inputs to be considered: pattern and text. A k-d tree, or k-dimensional tree, is a data structure used for organizing some number of points in a space with k dimensions. K-d trees are very useful for range and nearest neighbour searches.

In this paper, we studied and compared k-d tree algorithm and brute force algorithm on various levels. The use of the approximate k-nearest neighbour with K-d Tree data structure and comparing its performance attributes to the brute- force approach. In approximate nearest neighbour to evaluate and compare the efficiency of the data structure when applied on a particular number of points, distance and execution time. The work performed between two techniques and select the best one. The result of the work performed in this paper revealed better performance using the k-d tree, compared to the brute-force approach. The aim of the algorithm is to make faster, more accurate and efficient data structure primarily depends on a particular data set. It can be further expanded as by changing the k-d tree traversal technique. We have proposed a new modified traversal technique for k-d tree.

Keywords: Data Mining, Data Structure, Binary Search Tree, Nearest neighbour, Approximate K-NN, K-d tree, Brute-force.