Nearest Neighbor Search

Definition ::

Given a set of “objects” $X_1,\dots ,X_n$ and their pairwise distances $d_{ij}$

Various nearest neighbor problems ::

• Find the closest pair of points among $X_1,\dots X_n$
• Find all pairs of points that have distance smaller than some threshold - all pairs similarity search for example - or that have distance in a certain range - range search
• Find the k nearest neighbors of a particular point
• Find the k nearest neighbors of all data points
  • for example to build the k-nearest neighbor graph based on some objects etc

Applications ::

• Near duplicate detection - find entries in one - or several data bases that might be duplicates –> because they are rather close to each other
• A simplistic recommender system : simply recommend the item closest to the one the user just bought
• simple prediction of machine learning systems

Given there is some application within machine learning :

k nearest neighbor classifier ::

• Given pairs of objects $X_j$ with labels $Y_i$ for$i=1,\dots ,n$ the $X_i$ are the objects - say people, molecules, images etc - and the $Y_i$ are the corresponding “class labels “ - say male, female, cow, chicken etc… That data is called training data and ought to be categorized etc
• We want to use this data to construct a rule that can predict the class labels for new, previously unseen objects - test data
• k-nearest neighbor classifier is a simple approach to this problem

1. Assume we can measure distances between all objects
2. Given any new object X, find the k closest training objects $X_{i1},\dots ,X_{ik}$
3. Use the majority vote among their labels $Y_{i1},\dots ,Y_{ik}$ as the label Y for the new data point

![[Pasted image 20230127102846.png]] With given diagram we set a new point we ought to label accordingly. Once within a field of already existing data sets, we have to evaluate how to label them too. –> we search in a given radius and based on the majority of labels we categorize our new data point according to them.

abstract observation for nearest neighbor problems.

Different flaovr of neighbor problems :

• ALl nearest neighbors vs a single nearest neighbor
• Few queries vs many queries
  • If the set $X_1,\dots ,X_n$ it is fixed and we have to answer many nearest neighbor queries, then we can afford expensive pre-processing
  • If we just want to evaluate the nearest neighbor relationships once - for example, to build a kNN graph - then we dont want to use expensive preprocessing
• Exact vs. approximate nearest neigbors
• Which metric are we utilising ? –> euclidean space ?

Closest pair of Points ::

Problem description :

![[Pasted image 20230127103406.png]] Given n points in the plane of ${\mathbb{R}}^2$. What is the closest pair of points ?

This problem is one of the primitives in Computational Geometry - that is, a basic subproblem that occurs over and over again when solving more complex problems –> checking ranges of nearest points, detecting overlapping space with points etc.. ..

Bruteforce Solution ::

Compute the distance between all $n(n-1)/2$ pairs of poitns and take the minimum –> problem, we ought to calculate a lot! $\mathcal{O}(n^2)$ as the worst case runtime, not good .

Closest pair of points on a line ::

To abstract [[#Closest pair of Points ::]] we can observe everything as a line. If our points were all on one line, we could simply sort the points in time $\mathcal{O}(nlogn)$ and then compute the distances between the neighbors on the line This would take $\mathcal{O}(nlogn)$ overall Yet in higher dimensional spaces, this wont work anymore –> we would have to sort across a plane.

Divide and conquer approach ::

Idea ::

• Divide the space in left and right such that htere are the same number of points on both sides.
• Then recursively solve the problem on the left side an the right side.
• Eithe, the closest pair of points is on one of the sides. THen we are done and can return and merge.
• Or the closest pair is “across” the boundary. Then we have to do something clever when recombining the solutions

A possibility would be to span the shortest-found-distance $\delta$ as a tube about the dividing line. Within that tube we then could find a better solution of points within this small range. If we have found something, then we can set those to the closes pairs. However we have the problem of stacking points within the tube on one side –> that will be detected as smaller pairs, yet they are not finding the correct, expected pairs between two sets.

Storing the points at first ::

Let us first discuss how we “store” the points.

• We first sort all points according to their x-coordinates
• We store the list $P_x$ of x-coordinates in this order
• We do the same thing for the y-coordinates
• When separating the points into “left” and “right” we simply generate lists $P_{x,left},P_{y,left},P_{x,right},P_{y,right}$

So separating the whole structure is rather easy. One seperation step can easily be done in time of $\mathcal{O}(n)$ we just copy the arrays - note that to find the points left and right is easy in constant time, as we split right in the middle, but we need to copy the arrays later anyway to construct yet another one, $A_{\delta }$

Solving the problem of smallest pairs that are divided into left/right side

1. Assume that the closest pairs on the left and right sides have distances at least $\delta$
2. Then overall the closest pair can only be “across” the boundary if there exists a point within a $\delta$-strip to the left and the right of boundary

Now we put all point that are in the $\delta$-region in a new array $A_{\delta }$ that is sorted by y-values . ![[Pasted image 20230127111908.png]]

Problem persists, that further points stacked in x axis for example are within the delta range and have to be observed, although we are sure they are not necessary within –> cus if they were, then we would’ve found them before and thus didnt need to observe them anymore.

We could construct a circle around all the points within $A_{\delta }$ yet that is also time consuming and we are messing around with circles- which is awful.

==Solution==

Consider a point within the Array $A_{\delta }$. We need to look at all points that have ==at most== distance $\delta$ in y-direction. Not that all pairs of points on the same side have a distance of at least $\delta$ –> otherwise we would’ve found them already.

HOw many such points in the “square above p” exist?

![[Pasted image 20230127112241.png]]

To observe we can place at most 4 points within a square of distance $\delta$

So our idea is to position a given set of those squares on both sides - left and right..

All in all we only need to consider at most 7 points above and 7 points below the chosen point. ![[Pasted image 20230127112341.png]]

==To find out whether== p has a neighbor that is closer than $\delta$, we simply compute the distance of p to the 7 points before and after p in Array $A_{delta}$

![[Pasted image 20230127112721.png]]

not that in $A_{\delta }$ we do not konw whether a point is left or right

• In fact, we can only look that the 7 points behind p in the array - otherwise we make all computations twice when going through the list of points p.

Algorithm ::

1. Given, a set of P of points in ${\mathbb{R}}^2$
2. We first build the list $P_x$ and $P_y$ by sorting – for each dimension!
3. These list are the input to the following closest pair algorithm ::

ClosestPair(Px , Py )  
	if |P| ≤ 3 # end of recursion  
		find closest pair by computing all distances  
	# Recursion: split in left and right part  
	Construct Px,left , Py ,left , Px,right , Py ,right  
	(l0, l1) = ClosestPair (Px,left , Py ,left ) # solve left part  
	(r0, r1) = ClosestPair (Px,right , Py ,right ) # solve right part  
	# Combine solutions:  
	δ = min{dist(l0, l1), dist(r0, r1)}  
	Build list Aδ  
	For each p ∈ Aδ , compute distance to next 7 points in Aδ  
			Let δ′ be the minimal distance achieved in this way, for points p0, q0  
			if δ′ < δ  
		 Return (p0, q0)  
	 else

Running time ::

1. We first need to sort the points to build $P_x,P_y$, this takes time $\mathcal{O}(nlogn)$
2. Then we split each part into two equal sized subproblems
3. To combine the two sub-solutions, we need to go through all points and check whether they are in the $\delta$-stripe $⟶\mathcal{O}(N)$
   1. Note that theoretically, all n points could be in the $\delta$=strip
   2. For all these points we then need to compute a constant = 7 number of distances
4. Together this gives us an recursion of $T(n)\le 2T\frac{n}{2}+cn$ With the Masters theorem, this leads to $\mathcal{O}(nlogn)$

Caveats ::

In principle, the algorithm can be generalized to higher dimensions But if the dimension is large, it increasingly gets inefficient ::

• the number of points that have distance $\delta$ from each other and sit in the same little squares grows exponentially with the dimensions points to computer = $2^d$
• So instead of just looking at 7 points ahead, we need to look ahead much further - eventually we have to look at all points within the array.

Randomized Solution in linear time ::

Instead of systematically traversing through the whole set of points by dividing them in uniform sizes at each step, we could try a more random approach :

The idea would be :

Idea :

1. First select $\sqrt{n}$ points at random and compute their pairwise distances by brute force - takes around $\mathcal{O}(n)$ time.
2. From the whole set of distances, set $\delta$ to be the smallest of all of them –> only observing from the random notes we observe
3. Now divide the space into a grid of square with side length $\delta$ - not that the number of grid cubes might be large with unfortunate point selection –> not guaranteed to be efficient!
4. Call a square filled if it contains at least one of the n original points.
5. We are aware that the closeest pair has a distance $\le \delta$. Thus the closest pair of points has to lie in the same or in neighboring squares within our grid!
6. To find the closest pair we have to do the following ::
   1. For every filled square, compute the closest pair among the points in this square by brute forcing
   2. For every pair of adjacent squares, compute the closest pair among all the points in the two squares by brute forcing too

Analysis ::

1. Denote by $f_k$ the number of points in the k-th filled square.
2. Then the cost to compare points within the square k are $\mathcal{O}(f_k^2)$
3. The cost to compare points in neighboring squares k and i are therefore $\mathcal{O}(f_k\ast f_i)$
4. ==One can show that the sum of all these costs is done in $\mathcal{O}(n)$, with a high probability! Not guaranteed tho!== The key for this analysis L analyze the grid width g
   1. g must not be too small : then we would need to sample more than $\sqrt{n}$ points in the first step to achieve this grid width, and applying brute force on this sample would be beyond linear time again
   2. Yet g must not be too large either, because we use brute force inside the squares –> increases with larger squares One particular reason why the analysis is so complicated: the distances of the sampled points are not independent from each other – people realized that it is easier to sample distances instead of points, this made it way easier. But was disccovered later! –

As a result, we now have a randomized algorithm with the following properties ::

1. The running time of this algorithm is $\mathcal{O}(n)$ with a high probability
2. it always returns the correct result because of definitino

Loose ends : probable issues ::

The origianl paper by Rabin left one open problem :

how can we decide which of the squares are filled, without walking through all of them? Note that there might be much more than $\mathcal{O}(n)$ squares, which would then spoil the $\mathcal{O}(n)$ bound we found earlier.

It was fixed by Fortune / Hopcroft by implementing perfect hashing in 1979. Was further optimized by Diezfelbinger with the use of almost universal hashing

Takeaway ::

This algorithm is cool! Its simple, improves from $\mathcal{O}(nlogn)$ to $\mathcal{O}(n)$ and relatively simple too