# Tag Info

6

Without storing points in the inner nodes, but the cut value and cut coordinate, one can use this algorithm to perform NN search: Procedure NN(node), given query q if(node is leaf) Search all points, in node, update current best else {internal node} if( cut_coord(q) <= node's cut-value ) NN(left-child) if( cut-coor(q) + ...

4

Use the space partitioning approach to nearest neighbor search. For instance, one approach is to use a $k$-d tree on on the surface of the sphere. You can express every point on the sphere using spherical coordinates: every point on the sphere has coordinate $(1,\theta,\phi)$. Thus, we have a 2-dimensional space with coordinates $(\theta,\phi)$. Now ...

4

Your algorithm starts at some vertex and then always move to the closest vertex that's not been visited so far. That's not guaranteed to find the minimum spanning tree, as the example in your question shows. First, in a general graph, the algorithm might get stuck: you might end up at a vertex where you've already visited all the neighbours. For example, ...

4

One optimization I would propose is over the brute force search: \begin{align*} d(\mathbf{x}_i, \mathbf{x}_j) &= \lVert (\mathbf{x}_i-\mathbf{x}_j) - \mathbf{v} \rVert^2\\ &= \sum\limits_{k=1}^N (x_i^k - x_j^k-v^k)^2\\ &= \sum\limits_{k=1}^N ((x_i^k-x_j^k)^2+(v^k)^2-2v^k(x_i^k-x_j^k))\\ &= \sum\limits_{k=1}^N ((x_i^k)^2+(x_j^k)^2-2x_i^... 3 It seems hard to imagine that your claimed running time is correct, for a method that works in an arbitrary number of dimensions. It sounds like you are claiming that your data structures works in an arbitrary number of dimensions (n), but the running time does not depend on the dimension (n). That seems unlikely; nearest neighbor search is known to be ... 3 You can do it in two binary searches. For simplicity I assume that all numbers are distinct and, even more, absolute differences between T and all other elements are distinct too. The solution is easily adapted if it is not the case. What means that a selected subrange is optimal? That means that we can't move it neither right (|A_{j+k} - T| > |A_{j} -... 3 Straight from definition: \sqrt{(q_1-p_1)^2 + (q_2-p_2)^2 + \cdots + (q_n-p_n)^2} In your particular case n = 3, so the query should also be 3D (e.g. {7, 4, 3}. \sqrt{(q_1-p_1)^2 + (q_2-p_2)^2 + (q_3-p_3)^2} So plugging in the third dimension:\begin{array}{|c|c|c|l|} \hline X1 & X2 (Kg/m^2) & X3 & \text{Square distance to query point ...

3

An octree or k-d tree are standard data structures for this sort of task, and should provide reasonably efficient support for all of the operations you listed.

3

It seems that the relevant data structure might be a dynamic Voronoi diagram. Voronoi diagrams are often the answer when a set of points on the plane is involved. In this case, since the point set is evolving, you want a dynamic version.

3

If I understand this correctly, most spatial indexes could be used. Spatial indexes typically have about $O(log{V})$ insertion time and similar lookup time for nearest neighbors. Of course you can create a Voronoi diagram from that, but you can also use the index directly to find the closest neighbors whenever you need them. For low dimensionality (2D, 3D)...

2

kNN tends to be exponential because the search space increases with $2^k$. Imagine you partition the space around your search point into quadrants. For k=1 you just have to search two 'quadrants' (higher and lower values), for k=2 it's 4 quadrants, for k=3 it's 8 quadrants, i.e. exponential growth of search space. That is what the kD-tree suffers from, ...

2

Your problem (at least the second variant) is known as 2D range searching. Commonly used data structures are range trees and k-d trees. Searching for range searching on the web will open you a window into the area. These lecture notes come up, for example.

2

Here are links to two different software packages that address your question. It may be worth studying each to see if the methods they employ satisfy your needs: (1) Matlab GridSphere. "A geodesic grid is an even grid over the surface of a sphere. The algorithm is optimized for a grid generated by GridSphere and won't work on an arbitrary geodesic grid." (...

2

You don't need sophisticated data structures or algorithms to handle this case. Exact match (r=0) just means that you want to store a set $S$ of points in a way so that, given $x$, you can test whether $x$ is in $S$. If you have a set $S$ and want to be able to query whether a point $x$ is in the set, then standard data structures suffice. You don't need ...

2

The Covertree is a specialized data structure for neighbour search. However I don't know it's update performance. A better option may be the PH-Tree (my own implementation). It is similar to a quadtree, but implemented as a prefix-sharing bit-level trie. Advantages: Maximum depth of the tree is 64 (assuming 64bit per dimension) No reordering, ever. This ...

2

Yes. Normalize the vectors, then use the Euclidean ($L_2$) distance. In particular, map the vector $v=(v_1,\dots,v_n)$ to the vector $$\tilde{v} = ((v_1-\mu)/s,\dots,(v_n-\mu)/s)$$ where $\mu=(v_1+\dots+v_n)/n$ is the mean of the elements and $s=\sqrt{(v_1-\mu)^2 + \dots + (v_n-\mu)^2}$. (In the special case where $s=0$, define $\tilde{v}=(1/\sqrt{n},\... 2 Found the paper finally. Not sure I've read exactly the same paper (maybe I read some SO or SE answer or some other paper that inspired/was inspired by this paper). Nethertheless, the algorithm is exactly the same. A Fast Algorithm for the All k Nearest Neighbors Problem in General Metric Spaces by Edgar Chávez and Karina Figueroa and Gonzalo Navarro. http:/... 2 Your problem is the same as listing all cliques in a graph. Given your weight matrix, construct a graph in which two vertices are connected if the weight between them is below the threshold. A clique in this graph is the same as the sets of vertices you are interested in. A graph could contain exponentially many cliques - even exponentially many maximum ... 2 I'm not familiar with dk-NNG, but have you tried a PH-Tree? It has excellent insertion times and very good kNN search. I tested several scenarios with up to 40 dimension and$10^6$and$10^7$points. It usually competes with R*Tree (R-Star-Tree) for kNN-search, but has much better update performance. You could also try an R*tree, they are almost always ... 2 Don't search for a formula – you'll probably never find something so specific. Instead, try to break up the task into smaller units. Since your arrays are binary, $$(A_i-B_i)^2 = \begin{cases}0 &\text{if }A_i=B_i\\ 1&\text{if }A_i\neq B_i\,.\end{cases}$$ So$\sqrt{\sum(A_i-B_i)^2}\leq 2$if, and only if there are at most four values of&... 2 Data structures designed to organize multi-dimensional data can help, for instance quad trees or, more generally, k-d-trees. It might also be possible to apply ideas from sweep-line algorithms, sweeping outwards radially from the current position of the robot. 2 Due to accuracy complications as well as loss of information I cannot convert them to Cartesian coordinates. I don't understand this restriction. Converting to Cartesian coordinates uses essentially the same trigonometric functions that you would need to find the distance between two points in spherical coordinates: the only fundamental difference is that ... 2 Distance metric learning It sounds like you want to learn a distance metric$D(\cdot,\cdot)$on the items. If the human tells you that A is more similar to B than to C, then you learn that$D(A,B) < D(A,C)$(probably). Based on many instances of this, you can learn a distance metric$D(\cdot,\cdot)$. Then, you can use$k$-nearest neighbors with this ... 1 Don't add the point between the closest pair of points; add it between the endpoints of the closest edge. 1 Cosine distance is common in Information Retrieval and other text-based scenarios because text is most easily represented as high dimensional sparse vectors in the word space. A few specific advantages of cosine distance over Euclidean distance are: it is fast and simple - particularly, since vectors are sparse, only dimensions present in both vectors need ... 1 Use any algorithm for all nearest neighbors; then you can trivially solve your problem. Such an algorithm finds, for each data point, its nearest neighbor. The most isolated point is the one whose nearest neighbor is farthest away, so once you've solved all nearest neighbors, you can find the most isolated point by a simple linear scan. Apparently all ... 1 If you have a voronoi diagram you have neighbour information of each$p$. You can use that to path search (using A* or even greedy depth first) to the 3 points that surround$q$. Then you can extract the closest from that. If the voronoi is stored as a binary tree where each line divides the space into half-planes then it's just a dive into the search tree. 1 You could do$|S|$iterations of a single-source shortest paths algorithms, one per vertex in$S$, then compute$\sum_{s \in S} d(s,n)$for each$n \in V$. If all edge lengths are non-negative, the running time to do this using Dijkstra's algorithm will be$O(|S| \cdot |E| + |S| \cdot |V| \log |V|)$. This may be faster than all-pairs shortest paths, ... 1 The Floyd-Warshall algorithm computes all-pair shortest paths in$|V|^3$time. Then you could compute the "shortest paths" from all nodes in$V$to the subset$S$by storing each shortest path in a$|V|$-size array, and sort these distances/array. First$k$values will give you the$k\$-nearest nodes.

1

You want a data structure that supports nearest neighbor search in 2D. There are many options, but a simple one that is widely used for practical situations is a quadtree data structure. It supports both efficient lookup and efficient insert operations.

Only top voted, non community-wiki answers of a minimum length are eligible