CODEWITHSUNDEEP
kdtreevlfeat
mugetsu
mugetsu

Reputation: 4408

slow kd-tree queries using vlfeat, faster alternatives?

I'm using vlfeat's kdtree which implements the kd-tree from FLANN, which supposedly handles high dimension data. However, right now I have a kdtree built from a 128x15000 set of data and kd tree queries for anything has slowed down to 8 seconds a query. Is this the limit of kd-trees? FLANN was supposed to be a faster optimized kdtree too...

what other options do I have now?

Upvotes: 2

Views: 1383

Answers (4)

Da Kuang
Da Kuang

Reputation: 892

My guess is that you were querying one data point at a time. Maybe you want to send all the queries as a matrix at once, like this function call from the documentation:

[index, distance] = vl_kdtreequery(kdtree, X, Q, 'NumNeighbors', 10, 'MaxComparisons', 15);

Note that it limits the number of MaxComparisons to be 15, which is the key part to achieve fast performance.

Upvotes: 0

rkellerm
rkellerm

Reputation: 5522

VLFeat implements both FLANN suggested algorithms (The multiple randomized trees and hierarchical k-mean trees). Maybe for your case the algorithm choice or the parameters set (or both) are incorrect. Try the original FLANN or OpenCV's FLANN implementation (Well, or implement your own based on VLFeat) to get the right algorithm and parameters.

Upvotes: 0

Stefan
Stefan

Reputation: 1206

Is it really that slow? What parameters/settings do you use?

Besides that I can recommend FLANN.

Upvotes: 0

fsrajer
fsrajer

Reputation: 11

Try using David M. Mount and Sunil Arya ANN (Approximate Nearest Neighbor Searching)

http://www.cs.umd.edu/~mount/ANN/

Upvotes: 1

Related Questions