Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Questions tagged [nearest-neighbour]

The point from the dataset that is closest to the query point.

43 questions
Filter by
Sorted by
Tagged with
101 views
+100

### Time Complexity for Nearest Neighbor Searches in kd-trees

Nearest neighbor searches in kd-trees run in logarithmic time, as shown by Friedman et al. However, I have some difficulty to fully understand the proof. In order to calculate the average number of ...
16 views

### Same Result of KNN and Decision Tree

Given a decision tree, is it possible to find a KNN classifier giving the exact same classification?
25 views

### What is the purpose of standardization in machine learning?

I'm just getting started with learning about K-nearest neighbor and am having a hard time understanding why standardization is required. Reading through, I came across a section saying When ...
29 views

### Is this computational complexity of the k-NN (custom distance) correct?

I read on a book that in general k-NN (no optimizations), given $d$ dimensions $n$ examples every computation of distance is $O(d)$. Since every example has to be compared with all the other ones, ...
548 views

### Condensed Nearest Neighbor Explanation

I have a question regarding the Condensed Nearest Neighbor algorithm from ...
13 views

### Best asymptotic randomized multidimensional index?

What data structure has the best asymptotic running time for nearest-neighbor search on multidimensional data? I am interested in both preprocessing time and query time, but let's restrict attention ...
22 views

### How to find all numbers that there distance from given point are less or equall to integer n? [closed]

Given a set of numbers $D$ and some number $k$ I want to find all numbers that are in $D$ such that the distance between $k$ and any found number is less or equal to integer $n$? Example: suppose we ...
29 views

### Placing a point between two nearest ones

I have a closed 2D shape expressed as a list of points, like that: [ {0, 5}, <-- {x, y} {10, 5}, {15, 6}, ... ] The user has a canvas: each time he ...
179 views

### Nearest Neighbor Search in Spherical Coordinates

I am familiar with k-d trees being used to find nearest neighbors (NN) in 3-D euclidean space however in my particular case I am given a huge array of spherical coordinates. Due to accuracy ...
178 views

### In most locality sensitive hashing implemensions of SimHash, why is the cosine distance used and not the euclidean distance?

In Chapter 3 of Mining of Massive Datasets, the basis of locality sensitive hashing is explained. They notably mention simhash for the cosine distance, where random hyperplanes are generated, and for ...
71 views

### Find the nearest sum to a given number of two elements in sorted matrix

Given a sorted $n\times n$ matrix $A$ of real values. That is $a_{ki}<a_{kj}$ and $a_{it}<a_{jt}$, when $i<j$. Propose and algorithm, finding two elements of this matrix with the sum nearest ...
68 views

### Counting arrays with Euclidean distance at most 2 from a given binary array

I have a binary array like this: $$A = [0,1,0,0,1,0]\,.$$ I'm trying to find a way to calculate how many arrays of the same length exist that have a Euclidean distance of 2 or less from this array. ...
412 views

159 views

### Support Vector Machines vs K-Nearest Neighbors

Let's say we have trained a Support Vector Machine with a Gaussian Kernel. When we feed our model an example, it classifies it based on its similarity to landmarks (distance to examples in our ...
55 views

### Approximate Nearest Neighbour Problem in Spherical Setting

There has been significant literature in solving the (Approximate) Nearest Neighbour Problem in the spherical setting in the $\mathbb{R}^n$ using Angular and Spherical LSH and other lattice sieving ...
160 views

### Data Structure for k Nearest Neighbour Search in D dimension using only point cloud as query points

I have a point cloud of N points in D-dimensional space with periodic boundary conditions, where N can range from 500 to 10^8 and D can range from 1 to 20. The distribution of points varies wildly, ...