performance on low dimensional datasets

[suimo]

I have tried this algorithm and flann on low dimensional dataset(3-d point cloud). Here are 800000+ map points, and 300 query points, and find the query points' k neighbor with this algorithm and flann. the setup of hnswlib is ef_construction = 40, M = 6. neighbor number k = 10 the performance of two algorithm as follows: index build time : hnswlib 2249.92 ms flann 207.523 ms search time : hnswlib 1.3619 ms flann 0.5652 ms and there are some difference between the search results of these two algorithm, the performance of hnswlib is worse than flann. Is this reasonable? I'm looking forward to some advice. here are my dataset and search result. flann_result.txt hnswlib_result.txt dataset.tar.gz

[searchivarius]

@suimo I believe HNSWLIB should have similar performance as HNSW in NMSLIB in terms of speed, but indexing is faster. However, I am getting 0.01ms at 90% recall. Also NMSLIB has the VP-tree that has 100% recall with 0.01 ms time. You can go a bit faster with 95%. Indexing is somewhat longer than HNSWLIB and noticeably longer than FLANN. I am not sure though that numbers are directly comparable, I am running on a laptop.

[yurymalkov]

Hi @suimo,

I'll look at the dataset and get back to you. When I did tests for d=4, hnsw was faster than flann and vp-tree( flann is the slowest).

[searchivarius]

@yurymalkov if I remember correctly you tested on random 4d. And numbers were pretty close. Actual 3d data has lower intrinsic dimensionality, which gives tree-based methods an edge.

[yurymalkov]

@searchivarius Hm, I am not sure why tree structures should be better at low dimensionality? A low-dim HNSW with exact Delaunay graph seems to be quite competitive (https://arxiv.org/pdf/1911.02788.pdf).

I've took a look at the dataset, the gt calculations seems to be noisy(depend on the order of calculation), so one needs to be careful with that (e.g. I've bumped into this problem).

On hnswlib you can get 0.99 in 0.005ms (1.5 ms for all queries), and if you add extension (like in nmslib's hnswlib), it will go down to 0.0025ms at 0.99 on an intel cpu in a single thread.

@suimo I wonder, what flann index did you use?

[suimo]

Hi, Thanks for your reply! I use KDTreeSingleIndex in flann. May be I didn't use the OpenMP to speed up. Could it be the reason that hnsw slower than flann?

[searchivarius]

@suimo if you are using OpenMP, it's not a fair comparison, of course. It is hard to find now a server that would have fewer than 8 actual cores! If you run multi-threaded queries in FLANN, you should run HNSW in the multi-threaded mode too and then compare query-throughput. BTW, regarding your data, could you tell me what's the source of the data?

[suimo]

I tested both algorithm in a single thread. And the dataset is collected from lidar sensor

[suimo]

By the way, I used a for loop to input the query point one by one.

[yurymalkov]

So, flann KDTreeSingleIndex does the "exact" search (assuming exact distance calculations). If you are running flann in a single thread (I would double check that by setting the cpu affinity) that does mean flann outperforms the HNSW in this scenario. I would also then try nanoflann (https://github.com/jlblancoc/nanoflann/).

The reason why HNSW might be slower than flann is because current HNSW implementation is space-agnostic. Spaces properties like triangle inequality and having the exact Delaunay graph can help for small dimensional spaces. If you add those to HNSW it might be faster than competitors (according to https://arxiv.org/pdf/1911.02788.pdf it is), but I am not aware of available implementation (maybe, ask authors? 100ns per query seems be pretty good if true).

Above-mentioned tricks however, do not help as dimensionality goes higher and do not help on majority of the datasets, so they are not included. 2D-3D points are the ones of the rare exceptions where it can help.

You can also try vp-tree as @searchivarius mentioned, but it is also space agnostic.

I you already have a GPU and time I would maybe dig into octrees. I heard that nvidia uses them or RTX processing, so probably there is some good implementation that can be adapted, but I am not sure.

[searchivarius]

@suimo is there publicly available LIDAR data? Maybe more generically, public robotics data for motion planning, it's relatively low-dimensional too. Thanks!

[suimo]

Hi, @yurymalkov Thanks for your detailed reply. I just used original flann(https://github.com/mariusmuja/flann). @searchivarius the dataset is collected from velodyne lidar(VP-16). There are some lidar points dataset on the KITTI Benchmark, I will do more tests on it.

[searchivarius]

@suimo thank you, and just one more clarification question on the use of OpenMP. So, do I get it right you FLANN was always 1-threaded and you made HNSW 1-threaded too, including indexing?

[suimo]

I just used the definition "#pragma omp parallel for" when building index, if not, the building time will be 12364.4 ms

[searchivarius]

@searchivarius are you talking about FLANN or HNSW? In general, it's not an apple-to-apple comparison anyways, b/c FLANN runs a parameter tuning algorithm. It takes a lot of time, but for a low-dimensional 3D data, it is kinda no-brainer that a single KD- or VP-tree index will be nearly optimal so this time is wasted. The index construction cost itself is very small compared to HNSW.

[suimo]

So it's better to use tree-based algorithm for low dimensional dataset, right?

[searchivarius]

@suimo I think for real 2-3d data tree-based solutions are really hard to beat. Plus, there are very specialized variants of trees, which we don't implement, but they can be good for 2-3d data. If you have 6d, tree-based can still work very well, but HNSW may be somewhat faster.

[searchivarius]

That said for 2-3d you can also construct exact Voronoi diagrams efficiently, which we don't do either. Then, 1-NN search becomes really fast. Not sure about k>1 though.

[suimo]

I got it.Thanks for your advice!