title: C++ Data Structure for k Nearest Neighbour Search in D dimension using only point cloud as query points
body: <p>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. 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 points exist within a distance of each point, specifically the maxnorm distance. I don't need to know which points are within the radius, just how many, but it would be a nice addition.</p>
  
  <p>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.</p>
  
  <p>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. One the positive side, it can natively handle the wrapping conditions, and as such doesn't require duplication.</p>
  
  <p>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 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:</p>
  
  <ul>
  <li>Handle a small and large number of points, i.e 500-10^8 points</li>
  <li>Handle up to 20 dimensions</li>
  <li>Work with periodic boundaries (i.e., a flat torus)</li>
  <li>Work with maxnorm distance (soft requirement. Euclidean can give me a potential list which I can manually cull, but maxnorm would be preferred)</li>
  <li>Can find k-NN to query point as well as find how many points exist with distance to query point</li>
  <li>Query points are only points in the structure, not arbitrary points</li>
  <li>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.</li>
  <li>Doesn't need to support insert or deletion.</li>
  </ul>
  
  <p>Thanks</p>