Questions tagged [nearest-neighbour]

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

Filter by
Sorted by
Tagged with
10 votes
1 answer
878 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 ...
user avatar
  • 200
8 votes
2 answers
674 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 \...
user avatar
  • 363
7 votes
2 answers
3k 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 ...
user avatar
  • 173
7 votes
2 answers
168 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 ...
user avatar
  • 201
7 votes
2 answers
990 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))$ ...
user avatar
  • 171
6 votes
2 answers
2k 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$ ...
user avatar
  • 227
5 votes
1 answer
841 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 ...
user avatar
4 votes
1 answer
147 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,...
user avatar
  • 349
4 votes
1 answer
833 views

Find the closest string to a fixed set of strings

I want to find the closest string to a fixed set of strings. The strings are all equal in length, and the number of strings in the set is relatively small (compared to all the possible strings of the ...
user avatar
  • 218
4 votes
1 answer
788 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'...
user avatar
  • 141
4 votes
0 answers
37 views

Is there a name for the class of distance functions that are compatible with k-d trees?

The typical nearest neighbor search implementation for k-d trees prunes branches when the distance between the target and the pivot along the current axis exceeds the smallest distance found so far. ...
user avatar
4 votes
0 answers
70 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?)...
user avatar
  • 141
3 votes
2 answers
196 views

Efficient Data Structure for Closest Euclidean Distance

The question is inspired by the following UVa problem: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&category=18&page=show_problem&problem=1628. A network of ...
user avatar
3 votes
2 answers
3k 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 ...
user avatar
3 votes
1 answer
9k 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 &...
user avatar
3 votes
1 answer
513 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 ...
user avatar
3 votes
1 answer
138 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 ...
user avatar
  • 151
3 votes
1 answer
88 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 ...
user avatar
  • 9,325
3 votes
0 answers
31 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 ...
user avatar
  • 131
3 votes
0 answers
173 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, ...
user avatar
3 votes
0 answers
516 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 ...
user avatar
2 votes
1 answer
844 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 ...
user avatar
  • 251
2 votes
1 answer
465 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$. ...
user avatar
  • 175
2 votes
1 answer
420 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 ...
user avatar
  • 121
2 votes
2 answers
496 views

How to find the nearest point in the coordinate system

There are so many points in the coordinate system. When a specific point is given in the coordinate system, I want to find the closest point to the straight line distance. For example, if you have 800 ...
user avatar
  • 121
2 votes
2 answers
68 views

A data structure that makes finding close objects easy

I’m working on a project that involves a robot and a very large number of reference points. The robot moves around, while the reference points are fixed in space. I would like the robot to be able to ...
user avatar
2 votes
1 answer
83 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 ...
user avatar
  • 829
2 votes
1 answer
43 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 ...
user avatar
2 votes
1 answer
203 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})$...
user avatar
  • 137
2 votes
2 answers
101 views

Looking for an efficient algorithm quickly find the nearest line (defined by perpendicular distance) to an arbitrary point

I have a large set of lines in 2D with a known start point and end point, and would like to find the nearest (defined by perpendicular distance) of those edges (or the extension of those edges past ...
user avatar
  • 23
2 votes
2 answers
2k 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 ...
user avatar
  • 23
2 votes
2 answers
43 views

Nearest line-segment to a query point or conversely

I have a set of line segments (say 1000 of them) and a query point. I want to find the segment which is the closest in the Euclidean sense (if the point does not project on the segment I accept two ...
user avatar
  • 3,912
2 votes
0 answers
67 views

Bowyer-Watson Delaunay Triangulation neighbour walk in $O(n^{1/d})$

The Bowyer-Watson Algorithm for creating Delaunay Triangulations works iteratively. Let's say that we have a Delaunay triangulation of $n-1$ points. Now we add the $n$-th point. In order to update the ...
user avatar
2 votes
0 answers
23 views

Does there exist a locality sensitive hashing for $\ell_p$-norm distance where $p>2$?

It is well known that the $p$-stable distribution can be used to generate locality sensitive hash code for $\ell_p$-norm distance measure where $p \le 2$. However, it seems that the situation for $p&...
user avatar
  • 258
2 votes
0 answers
17 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 ...
user avatar
  • 121
2 votes
0 answers
36 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 ...
user avatar
2 votes
0 answers
248 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-...
user avatar
2 votes
1 answer
116 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 ...
user avatar
1 vote
2 answers
111 views

kdtree or balltree supporting insertion/deletion

I'm looking for a data structure to perform nearest-neighbor searches in 3D Euclidean space. I have used kd- and balltrees for this purpose before, but my problem is more sophisticated this time. I'd ...
user avatar
1 vote
1 answer
37 views

A nearest neighbor data structure for meshes

I am trying to find a lightweight data structure to find the nearest neighbor mesh (a mesh being a collection of non-unique triangles) for a given point in R3 (3D Euclidean space). I have seen nearest ...
user avatar
  • 157
1 vote
1 answer
80 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, ...
user avatar
1 vote
1 answer
18 views

How to give the nearest text that the user has written

In my database I have 1500 food dishes, not all are single words, there are compound words like "cheese with dried fruit and nuts". And I have them in 5 languages (de, en, fr, es, it). My ...
user avatar
  • 111
1 vote
1 answer
96 views

Nearest neighbor search in latitude/longitude coordinates

I have two sets of lat/long points, $A$ and $B$. For each point $a$ in $A$, I want to find the corresponding closest point (by Haversine distance) $b$ in $B$. I'd like to use a space-partitioning tree,...
user avatar
1 vote
1 answer
74 views

Distance to $k$th nearest neighbor efficiently for arbitrary $k$

Problem. Given $X$ a finite metric space of cardinality $n$, construct a data structure in subquadratic time such that the query ...
user avatar
  • 113
1 vote
1 answer
188 views

Algorithm to find what points are the nearest to other points

I have two lists: Location list, it contains point of interest People list, it contains coordinates of every person. One single person could be in the list multiple times, depending from the log ...
user avatar
  • 13
1 vote
1 answer
366 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 ...
user avatar
1 vote
1 answer
605 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$, ...
user avatar
  • 111
1 vote
0 answers
11 views

What datastructure to query nearest neighbor with constraint on parameters

I have about 200'000 data points distributed on the unit-sphere. Aside of each point's location on the unit-sphere, it has also assigned a width and height. I can perform nearest-neighbor queries by ...
user avatar
1 vote
0 answers
14 views

Batching multiple nearest surface queries: Is it faster? Are there better algorithms?

I'm working on an algorithm that computes lots of "nearest point on a triangulated surface" queries in 3d as a way to resample data sets, and I'm wondering if there is any information out ...
user avatar
1 vote
0 answers
27 views

How to cluster N sets into N subsets ,so that we can determine which set a point is from by checking its nearest neighbor in aforementioned subsets?

Question 1: Given N sets of points $S_1$ ... $S_n$ (no intersection between $S_i$ and $S_j$ when i != j), I want to find subsets of $S_1$ ... $S_n$ (call them $T_1$ ... $T_n$ respectively) So that ...
user avatar
  • 61