Questions tagged [nearest-neighbors]
The nearest-neighbors tag has no usage guidance.
16
questions
13
votes
5
answers
1k
views
Repeated nearest neighbor calculation for millions of data points too slow
I have a dataset running into millions of data points in 3D. For the calculation I am doing, I need to calculate neighbor (range search) to each data point in a radius, try to fit a function, ...
7
votes
3
answers
8k
views
Performance of kd-tree vs brute-force nearest neighbor search on GPU?
I wonder if there is any study that compares the performance of kd-tree vs brute-force nearest neighbor search on GPU. Post #4 on this page suggests that kd-tree may not be the optimal algorithm for ...
- 173
6
votes
2
answers
2k
views
$k$ nearest neighbors for $n$ points with periodic boundary conditions in R^3
Take $n$ points ${\bf r} =\{ r_1 = (x_1,y_1,z_1), r_2=(x_2,y_2,z_2) \ldots r_n=(x_n,y_n,z_n) \}$ enclosed in a periodic box of length $L$, such that that the point $(0,0,0)=(L,0,0)$, $(0,0,0)=(L,L,L)$,...
- 163
5
votes
1
answer
298
views
Maximum and Minimum distance from query point within bounding box
I'm reading an article regarding approximating sums using KD-trees (similar to FMM).
As part of the effort I'm trying to make sense of this article , which is cited.
I'm having trouble understanding ...
- 161
4
votes
1
answer
2k
views
MD Simulation: Reference for the Neighbor's List Method
With a rather basic knowledge in C++, I have written my own MD simulation code. Currently, I calculate forces in the most naive way: I go through all the atoms and account for their interactions. This ...
- 207
4
votes
1
answer
121
views
Numerically compute one-to-one mapping
I have a set of points defined by their coordinates $(x_1,y_1)$ after changing some parameters of the problem I obtain a second set of points defined by their coordinates $(x_2, y_2)$. There exists a ...
- 397
3
votes
2
answers
2k
views
Finding nearest neighbors using Jaccard distance for positive, real-valued vectors
Say we have $x_i, \ldots, x_n \in R ^ D$ with positive, real components and use Jaccard distance $d(x_i, x_j) = 1 - \frac{\sum_{d = 1}^D\min(x_i^d, x_j^d)}{\sum_{d = 1}^D\max(x_i^d, x_j^d)}$ to find $...
- 153
3
votes
1
answer
1k
views
Nearest Neighbors in radius via Z-order order curve?
Given a $M\times M\times M$ 3D cube grid $C$, how can I map the 3D grid-coordinates to 1D coordinates such that every cell's nearest neighbors can be represented by a continuous range of corresponding ...
- 185
3
votes
1
answer
3k
views
Fast nearest neighbor search, Latitude Longitude
Is there a fast nearest neighbor search algorithm that generates the nearest neighbors, not based on Euclidean distances but based on geographic distances over a set of latitudes/longitudes. The fast ...
- 259
3
votes
2
answers
766
views
Effective way to build the neighbor's list in MD
I'm trying to implement the following form of the cell/neighbor list method in my MD code. I have divided my simulation box into a fixed number of cells, and according to its positions, I have ...
- 207
2
votes
2
answers
72
views
Efficient Representation of (spatially sparse) spatial time series
Background
I have a huge dataset consisting of points (on a plane) together with a timestamp for each point. This is a collection of car GPS measures, giving us the location (latitude/longitude) of ...
- 23
2
votes
1
answer
228
views
$k$-Nearest Neighbor Search using examples
I want to perform $k$-Nearest Neighbor Search in multidimensional space, but not using for example $L_2$-distance. I want the user to specify some "similar"-pairs examples and then perform a search ...
- 213
1
vote
0
answers
229
views
Use of Morton Key to reduce number of grid points
I asked a question on Stack Overflow Performance Issue with VP Trees and Nearest Neighborsand I was not satisfied with the answer and so I thought I would reword my question for this site and post ...
user16555
1
vote
0
answers
675
views
How to choose (and many) threshold in Eigenface?
I edited my question trying to make it as short and precise.
I am developing a prototype of a facial recognition system for my Graduation Project. I use Eigenface and my main source is the document ...
- 31
0
votes
1
answer
92
views
Nearest neighbours with a subset structure
I have a set of points of $\mathbb{R}^2$ which is organised in subsets:
$$
\cup_{0\leq i<N} \left\{ P_i^j \in \mathbb{R}^2, 0\leq j<M \right\}
$$
For all $(i,j)$, I want to find $P_k^l$ in ...
- 362
0
votes
1
answer
327
views
Find closest Point based on orientation and Euclidean distance
I have a set of points P1(x1,y1), P2(x2,y2), P3(x3,y3), P4(x4,y4), P5(x5,y5) in the Cartesian plane. I am trying to find the closest point to P1 based on the ...
- 175