Hi guys, I am new to ML and was experimenting with kNN search algorithms.

I have very high dimensional data 1000+ dimensions. What data structure is best suited for such high dimensional data.

I can bring down the dimensions to apprix 150 using using PCA without being too lossy.

Even then I am having hard time finding techniques that work with such high dimensional data. I am not looking for Approximate NN search using LSH.

What is the best technique that can be used here, kd tree doesn’t work well with high dimensional data, would Rtree or ball tree be a better choice or something different?

  • resented_ape@alien.topBEnglish
    1·
    1 year ago

    I understand your investigative spirit but I think you are going to discover that all methods of finding exact kNNs are different flavors of “slow” at high dimensions. There might be some exotic variations that can shave off some of the constant factor but they are usually restricted to Euclidean or inner-product-like distances (although that’s usually what people want). FWIW 8000 points doesn’t seem like a huge dataset.

    Here’s some R code and timings using the FNN package which has a few options:

    data8k <- matrix(rnorm(n=8000 * 1000), nrow = 8000)
system.time(knn <- FNN::get.knn(data8k, k = 30, algorithm = "brute"))
   user  system elapsed 
  70.19    0.06   75.87 
system.time(knn <- FNN::get.knn(data8k, k = 30, algorithm = "kd_tree"))
   user  system elapsed 
  78.51    0.14   85.08 
system.time(knn <- FNN::get.knn(data8k, k = 30, algorithm = "cover_tree"))
   user  system elapsed 
 129.52    0.14  134.01 
system.time(knn <- FNN::get.knn(data8k, k = 30, algorithm = "CR"))
   user  system elapsed 
  70.41    0.08   74.40

    That’s single-threaded on my very-much no-longer-impressive laptop. The fact that brute force search does so well in comparison to the others suggests that there aren’t good options for your data.