Nearest Neighbor Visualizer

May 6, 2010 in Nearest Neighbor Visualizer

The following images show a nearest neighbor interface I wrote with Python & pyOpenGL a few months ago.  Nearest neighbor is a fairly simple and commonly used algorithm with applications in pattern recognition, machine learning, DNA sequencing and many others.  I was specifically looking at comparing brute force search with the Kd-Tree algorithm for partitioning 3 dimensional spaces with nearest neighbors.  The visualizer places points in a 3dimensional array with user input to dynamically increase/decrease the number of field points & attractor points.  The colored spheres represent the attractor points and the smaller points represent the field.  As the user increases/decreases the number of field and/or attractor points they can dynamically calculate the nearest neighbors using either the brute force or Kd-tree search algorithms.  The field points will change color to indicate that particular point’s nearest neighbor.  The user can orbit the space and zoom in/out as they adjust the number of points and attractions.

“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. The problem is: given a set S of points in a metric space M and a query point q ∈ M, find the closest point in S to q. In many cases, M is taken to be d-dimensional Euclidean space and distance is measured by Euclidean distance or Manhattan distance.” – Wikipedia

“In computer science, a kd-tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. kd-trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches). kd-trees are a special case of BSP trees.” – Wikipedia

“The kd-tree is a binary tree in which every node is a k-dimensional point. Every non-leaf node can be thought of as implicitly generating a splitting hyperplane that divides the space into two parts, known as subspaces. Points to the left of this hyperplane represent the left sub-tree of that node and points right of the hyperplane are represented by the right sub-tree. The hyperplane direction is chosen in the following way: every node in the tree is associated with one of the k-dimensions, with the hyperplane perpendicular to that dimension’s axis. So, for example, if for a particular split the “x” axis is chosen, all points in the subtree with a smaller “x” value than the node will appear in the left subtree and all points with larger “x” value will be in the right sub tree. In such a case, the hyperplane would be set by the x-value of the point, and its normal would be the unit x-axis.” – Wikipedia

Advertisement