3
$\begingroup$

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 vertices using $L_2$ metric with additional constraint that are no further than $d$.

There are only insertions (in batches of $10^6$ points) and neighbourhood retrieval queries used. The results have to be exact - I cannot use approximate nearest neighbours or reduce dimensions.

The setting is following:
There are 50 dimensions, not correlated. The $k=9$ is number of neighbours, $d$ is given distance. The data is sparse in every dimension, mean and median are meaningful, data is random and unstructured in any way (but for sure not from uniform or Gaussian distribution).

So far I have tried to build parallel kd-tree with partial rebalancing, the ball trees, m-trees, r-trees, Sparse ktree (octree with more dimensions) partitioning and two-projection hashes. But I am facing problem, that either insertion time is far too long or k-nng queries are too long. I think this happens because the structures are either static or not really prepared to maintain full neighbourhood graph.

I have tried linear scan, it performs good for very small data, worse than z-curve localised version or sparse ktree. Up to some $n$ it outperforms any treelike structure. I made one modification to naïve algorithm: used one AVL (right threaded) per dimension keeping nodes connected among trees and checked only points within distance $d$ at each dimension - this one performs well, but due to its memory consumption and lack of multidimensional structure scales poorly.

What data structure would be the best in practice for dk-NNG?
If this is not enough, I would like to optimize the number of neighbours checked, for localised data the number of bins traversed.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

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 faster than a standard R-Tree. An implementation in Java can be found here.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your answer, good to meet the author of marvelous library. Indeed it is comparable with R*Tree, even better due to my tests, I have tried it about month ago. The k-NNG - it is just k-NN for every point, and instead of raw info about the neighbourhood it returns graph. Your implementation has very nice per query time, but since I use all points, and query always start from existing points, it isn't really exploited. +1 from me, maybe it doesn't solve the problem, but it is one of the top trees, quite compact in memory. $\endgroup$
    – Evil
    Jul 4, 2017 at 17:49
  • $\begingroup$ Thanks, good to hear that the library is useful for other people :-) $\endgroup$
    – TilmannZ
    Jul 4, 2017 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.