# 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, from completely uniform to very clumped together, however, each dimension is restricted to the range [-pi, pi). For each point in the point cloud I need to find the k nearest neighbours to that point. I also need to find how many (but not exactly which) points exist within a distance of each point. Both of these need to be done with maxnorm distances.

I've tried kd-trees, but they don't handle the wrapping boundaries, and for the larger trees, duplication is not feasible. Additionally, it gets slow at higher dimensions.

I've just come across Vantage Point Trees, and tried out some code, but it is slower than the kd-tree. Although, the code I found uses a recursive search method, with no batching. On the positive side, it can natively handle the wrapping conditions, and as such doesn't require duplication.

I'm about to see if I can squeeze some more performance out of the VP tree by converting to an iterative approach and seeing if I could batch search, but I had a thought. All these data structures work for finding nearest neighbours to arbitrary query points, while my query points are restricted to being points already in the point cloud. I figure this restriction might allow for some more performant structure (maybe a nav-mesh of sorts?). I tried searching for structures that would handle this, but my google-fu is failing me. So just wondering if anyone knows of a data structure that can handle the following:

• Handle a small and large number of points, i.e 500-10^8 points
• Handle up to 20 dimensions
• Work with periodic boundaries (i.e., a flat torus)
• Work with maxnorm distance (soft requirement. Euclidean can give me a potential list which I can manually cull, but maxnorm would be preferred)
• Can find k-NN to query point as well as find how many points exist with distance to query point
• Query points are only points in the structure, not arbitrary points
• Queries can be batched. i.e I need to find the k-th NN for every point in the point cloud. I also need to find how many points exist within d[i] for each point i. That is each point has a different search radius.
• Doesn't need to support insert or deletion.

Thanks for any help

• still care for an answers after all this time? – Walter Feb 4 '17 at 15:43