Questions tagged [nearest-neighbour]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
25 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, ...
0
votes
1answer
232 views

Condensed Nearest Neighbor Explanation

I have a question regarding the Condensed Nearest Neighbor algorithm from ...
2
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
3
votes
1answer
136 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 ...
1
vote
1answer
141 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 ...
2
votes
1answer
58 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 ...
0
votes
1answer
60 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. ...
8
votes
2answers
301 views

How to efficiently compute the most isolated point?

Given a finite set $S$ of points in $\mathbb R^d$, how can we efficiently compute a "most isolated point" $x\in S$? We define a "most isolated point" $x$ by $$x = \arg\max_{p \in S} \min_{q \in S \...
2
votes
1answer
69 views

How to embed Pearson distance into Euclidean space

I have a lot of numerical vectors, each of dimension 1000. I would like to compare them according to their Pearson distance. This works fine but comparing all vectors to each other is quadratic time ...
2
votes
0answers
32 views

Fast searching time for nearest neighbours

I am using KD trees to do nearest neighbour searching. My understanding is that it takes $O(n \log n)$ effort to create the tree where $n$ is the number of points and that it takes $O(m \log n)$ to do ...
3
votes
1answer
89 views

Cannot find paper: All k nearest neighbors search in N*log(N) using distance indices for log(N) support points

I remember reading a paper about finding k nearest neighbors for all N multi-dimensional objects in the set. I've tries to find it again many times, but have failed so far. The algorithm was as ...
4
votes
0answers
55 views

Repeated nearest-neighbor queries

If I want to make N repeated (i.e. millions of) 2D nearest-neighbor queries on a pointset of size M, is traveling down into a KD-Tree most efficient or are there better ways to do this? (e.g. Voronoi?)...
1
vote
1answer
57 views

Find all group of neighbors with a constraint weight

Forgive if this seems like a repeated question. However, I couldn't find a specific algorithm to my needs. I have nodes that have weights with each other. I want to find all unique groups of nodes, ...
5
votes
2answers
1k views

Finding k-nearest neighbors to a set of nodes in a large graph

Given a large graph $G=(V,E)$, a set of nodes $S\subseteq V$, the problem is finding the $k$-nearest nodes in $V$ to the nodes in $S$. Given a pair of nodes $(u,v)$, the distance $d(u,v)$ between $u$ ...
3
votes
1answer
68 views

What is the best known data structure for online dk-NNG?

I want to build the distance constrained k-Nearest Neighbours Graph, i.e. for every point $p$ in the data cloud $P$ there are at most $k$ undirected edges to points that are closest among all possible ...
1
vote
1answer
467 views

Finding the nearest neighbour of an existing 2d point in a set of points within $\mathcal{O}(\log{}n)$ time

Question Is it possible to find an existing point's nearest neighbour within a logarithmic upper bound? What I've tried I have: the set of points $P$, a point $p$, where $p\in P$, a point $q$, ...
2
votes
1answer
376 views

Searching a sorted array to find the $k$ closest values to a target value $T$

Let $A$ be a sorted array of $N$ values. I am interested in finding the index $j$ such that the elements $A_j, A_{j + 1}, ..., A_{j + k - 1}$ have the $k$ closest values to the given target value $T$. ...
2
votes
0answers
162 views

How can I improve my KNN classifier?

I'm trying to teach myself a bit about machine learning, so one of the first things I did was implement a KNN classifier in ruby. My goal was to classify text product reviews into 8 classes: books-...
2
votes
2answers
751 views

All nearest neighbor in a changing 2d euclidean space

I am in need of an algorithm for a part of a game (a mod) I am making. I have abstracted the problem: Given a 2D space with $N$ random points $p_1...p_n$, calculate the nearest neighbor of each of ...
2
votes
1answer
33 views

Nearest neighbour based on subjective human comparison - is this a thing?

I am looking for some clues as to the type of algorithm/data structure or general field of CS to look into... I have a collection of items that I would like to have a human subjectively compare such ...
2
votes
1answer
235 views

What is the state of the art for k nearest neighbour search?

I'm not an computer scientist, but still use/have an algorithm to find the $k$ nearest neighbours from a cloud of $N$ points in $d$ (my case $d=3$) dimensional space using some distance measure (in my ...
0
votes
2answers
112 views

How can I make k nearest neighbor queries fast on unit hypersphere?

I have $m$ points $D = \{x_1, \dots, x_m\}$ with $x_i \in \mathbb{R}^n$. After some preprocessing / building up data structures for those points, I get $T$ queries $y_i \in \mathbb{R}^n$ with $i=1, \...
1
vote
1answer
165 views

Using k-NN for Exact Match in Hamming Space (after Multi-index Hashing)

Before the Question: Greene, Parnas and Yao presented a scheme which, for binary data chosen uniformily a random, retrieves all points within Hamming distance r of a given point in time $O(d n^{r/d})$...
0
votes
0answers
234 views

What is the advantage of product quantization?

I'm reading Product Quantization for Nearest Neighbor Search. Quoting page 4: The strength of a product quantizer is to produce a large set of centroids from several small sets of centroids: ...
3
votes
1answer
6k views

k-nearest neighbors (Euclidean distance): How to process multiple attributes?

Given this sample: $$\begin{array}{|c|c|c|} \hline X1 & X2 (Kg/m^2) & \text{Class} \\ \hline 8 & 4 & A \\ \hline 4 & 5 & B \\ \hline 4 & 6 & B \\ \hline 7 & 7 &...
0
votes
0answers
138 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 ...
1
vote
1answer
52 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 ...
3
votes
0answers
157 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, ...
4
votes
1answer
136 views

Finding pairs of points that have a given offset

Problem: Given a set of points $S = \{x_1, x_2, x_3, ..., x_n\}$ from $\mathbb{R}^m$ and an offset vector $v \in \mathbb{R}^m$, find a set $Z \subseteq S \times S$ containing $k$ pairs of points $(x_i,...
6
votes
2answers
110 views

A key-value datastructure with fast (on average) member move and nearest neighbors search?

I have a 3 dimensional float key search space (say a simulation world). I want to keep my values (ints, agent ids) in a data structure that can perform nearest neighbors search (with search for N ...
3
votes
2answers
2k views

Is the Nearest Neighbor Algorithm a valid algorithm to find a Minimum Spanning Tree?

I just wrote a program that runs the Travelling Salesman Problem using the Nearest Neighbor Algorithm. Afterwards, I started looking into Minimum Spanning Trees (MST). From my understanding: The ...
8
votes
1answer
676 views

Why Is KD-Tree-based Nearest Neighbor Exponential in K?

I've read in many papers on higher-dimensional nearest neighbor search that KD-Trees are exponential in K, but I can't seem to determine why. What I'm looking for is a solid runtime-complexity ...
7
votes
2answers
2k views

Find k nearest neighbors on a sphere

Given a set $S$ of $N$ points on a sphere, and another point $P$ on the sphere, I want to find the $k$ points in $S$ that are the closest (Euclidean or great circle distance). I'm willing to do a ...
3
votes
1answer
531 views

Best data structure for high dimensional nearest neighbor search

I'm actually working on high dimensional data (~50.000-100.000 features) and nearest neighbors search must be performed on it. I know that KD-Trees has poor performance as dimensions grows, and also I'...
3
votes
0answers
459 views

Why is exact nearest neighbor search hard in high dimensional spaces?

I started research on nearest neighbor search in IR a couple of weeks ago. I am still very new to this field, but what I discovered so far from literature is: 1) For the exact nearest neighbor ...
4
votes
1answer
643 views

n closest points in a set of lat/long coordinates

Here's my problem: I have a website where people can search based on their location (which is converted to lat/long coordinates). I have many products stored in a database with their lat/long ...
7
votes
2answers
544 views

Fast and space efficient data structure for nearest neighbors in 3 dimensions?

I am looking for data structures to answer nearest neighbor queries in 3D which are reasonably space efficient (ie use at most $O(n^{1+\epsilon})$ space) and fast ($O(n^{\epsilon})$ or $O(log^k(n))$ ...
2
votes
1answer
640 views

kd-tree stores points in inner nodes? If yes, how to search for NN?

The link in wikipedia about kd-trees store points in the inner nodes. I have to perform NN queries and I think (newbie here), I am understanding the concept. However, I was said to study Kd-trees ...