What is algorithm used in rangesearch function in matlab

Hi

I worked with rangesearch function in Matlab for my project. https://uk.mathworks.com/help/stats/rangesearch.html

It does work well.

I would like to get your advice if it is relevant.

What is the algorithm behind the rangesearch function in matlab?

I found several papers about the fixed-radius nearest neighbor but i'm worry if the algorithm i write in my paper is not the actual algorithm applied in rangesearch function in Matlab

Thanks in advance

Answer 1

[Walter Roberson]

https://www.mathworks.com/help/stats/rangesearch.html#bs33ct8-8

KD-Tree.

[amj]

Hi Walter Roberson,

Thanks for your comment.

From this url: https://uk.mathworks.com/help/stats/rangesearch.html#bs33ct8-8

I applied this function :

[idx,D]= rangesearch(X,Y,r,Name,Value)

From my understanding, the function will apply either KDTree or exhaustive if i specify the nearest neighbor method in NSMethod parameter. If not, it will use the the fixed-radius search ..am i correct?

It is mentioned in this link:

For definitions, see Distance Metrics .

[Walter Roberson]

There is no "nearest neighbor method" in NSMethod parameter.

If you want nearest neighbor search use knnsearch() not rangesearch()

[amj]

Dear Walter Roberson,

Thanks for reply. It is mentioned in here:

https://uk.mathworks.com/help/stats/rangesearch.html#bs33ct8-8

If we specify the Nearest neighbor search method in 'NSMethod' as KDtree, It will creates and uses a kd-tree to find nearest neighbors or vice verca.

And also mentioned in here:

Alternatives

rangesearch is the ExhaustiveSearcher function for distance search. It is equivalent to the rangesearch function with the NSMethod name-value pair set to 'exhaustive'.

rangesearch is the KDTreeSearcher function for distance search. It is equivalent to the rangesearch function with the NSMethod name-value pair set to 'kdtree'.

My issue is, if i only provide in the rangesearch function parameter with radius value and distance metric (says Euclidean) and i did not specify any NN method either KDTree or exhaustive , what kind of NN approach used in the rangesearch function to find the nearest data points within a fixed radius?

[Walter Roberson]

The description of NSMethod says specifically the condition under which kdtree is used by default. Euclidian qualifies for kdtree but only up to 10 dimensions.

[amj]

Dear Walter Roberson,

Thank you very much for the confirmation

[amj]

Dear Walter Roberson,

One more thing please.

How can i know what is the single reference/paper/journal used in writing the rangesearch code so that i can put it in my paper? I found numerous versions of KDTree algorithm, one of them is from the github:

https://github.com/FNNDSC/matlab/tree/master/autodijk/kdtree

However, the KDTree algorithm explained in the book title does not include the use of a fixed-radius value in KDTree.The book title is : M. deBerg, M. vanKreveld, M. Overmars, and O. Schwarzkopf. "Computational Geometry: Algorithms and Applications" Springer, 2000.

whilst, the rangesearh function does include radius value to search the nearest data points. How can i know which author is responsible wrote the rangesearch function code so that i know which reference he/she used to produce the rangesearch code?

[Walter Roberson]

According to the KDTreeSearcher code,

%   References:
%     Friedman, J. H., Bentely, J. and Finkel, R. A. (1977) An Algorithm
%     for Finding Best Matches in Logarithmic Expected Time, ACM
%     Transactions on Mathematical Software 3, 209.

[amj]

Dear Walter Roberson,

Thanks a million. It is very helpful.

[amj]

Dear Walter Roberson, May i get a confirmation that the rangesearch function is rely on the said paper: An Algorithm for Finding Best Matches in Logarithmic Expected Time.

This is because, when i tried to detail out the algorithm, it seems questionable in the proposed algorithm II as shown in the appendix. May i know who is the author of this specific function code because i got few queries and i really need an urgent confirmation.

I don't know who i can contact from the matlab representative team to get a confirmation about the algorithm used in the code.

[Walter Roberson]

I have asked Mathworks for confirmation. I have no information about who the author of the code was.

[amj]

Dear Walter Roberson, Thank you very much for your help. How can i check the detail code of this function? Thank you very much

[Walter Roberson]

You can edit it by name.

edit KDTreeSearcher

[amj]

Dear Walter Roberson, Let me try. Thank you very much

[Walter Roberson]

Mathworks replied to me:

==== begin quote ====

I have reviewed the functions in the “KDTreeSearcher” class, and I can confirm that its default behavior corresponds to the k-d tree algorithm created by Friedman, Bentely, and Finkel and published in the paper you mentioned.

It is important to note that most functions that invoke the “KDTreeSearcher” class first build the k-d tree, then search it. The computational cost of building the tree is not considered by Friedman et al. in their published efficiently gains. For that reason, situations can be constructed where an exhaustive search algorithm can be more efficient than building and searching a k-d tree. If you are interested in determining the amount of time spent searching the tree, not building it, the following example code can be used:

>> x_data = rand(1e5,2);
>> y_data = rand(10,2);
>> r = 0.3;
>> profile on
>> rangesearch(x_data,y_data,r);
>> profile viewer

The time taken by the search algorithm is displayed next to “KDTreeSearcher.rangesearch”

[amj]

Dear Walter Roberson, Thanks a millions for your help. This confirmation is very helpful and significant. Thank you very much

Answer 2

[the cyclist]

There are typically two places to look for algorithm references for MATLAB function:

1. The documentation page for that function
2. Inside the function itself: Use "type function_name" to get a listing of the function, and look there (especially near the top of the file, but sometimes inline where subfunctions are called)

[amj]

Dear the cyclist Thanks very much