forum.alglib.net

Hello everyone,

I'm having this problem using the alglib .Net dll library.

when calling the following:
alglib.kdtree kdt;
nx=75;
ny=5;
normtype=2;
alglib.kdtreebuild(vectorlist, nx, ny, normtype, out kdt);

with vectorlist a 16384 x 80 matrix, I get the following exception
An unhandled exception of type 'System.StackOverflowException' occurred in alglibnet2.dll

Has anyone had this issue before? I can't seem to figure out what's causing it. As I have used this exact code before without having this issue.

EDIT: I generally observe this problem when there are a lot of vectors in the matrix with the same values. Does this cause problems for building a kdtree?
Would it be a problem if some vectors are exactly the same?

Thanks in advance.

Hello!

We've started investigating this issue, and will report first results at Monday. Thanks for your hint on duplicate vectors, it is very likely that problem is caused by duplicates in the dataset. Can you tell me - are these vectors mostly duplicates of ONE vector (say, 5.000 copies of same vector), or you have many small groups of different duplicates (10 copies of X, 15 copies of Y, 12 copies of Z and so on)?

Hello,

first of all, thank you for your reply :)

Upon testing it seems that the problem only occurs when there are a lot of vectors, specifically when the amount of duplicates reach a certain limit.
To place this in context:
I use the kdtree AKNN function to find nearest neighborhoods of a certain pixel in an image,
I take all pixels from a 5x5 patch, create a vector of size 5x5x3 = 75 and then fill in the R, G, B values in order of every pixel in the vector, i do this for every 5x5 patch from that image, thus creating a matrix of vectors.

When testing this on a 32x32 image with only 4 quadrants (big squares) of single colors no problems were observed,
only when doing this on a bigger image say 128x128 with a lot of similar 5x5 neighborhoods, thus generating a lot of equal vectors, this stackoverflow problem occurs.

So to answer your question accordingly, it happens in both situations (lots of duplicates of X, and lots of duplicates of X and Y and so on..) but only when the amount of duplicates of a certain vector reaches a certain unknown limit, so if there are a lot of vectors but only a few duplicates of some vectors no problems occur, only when there are a vast amount of duplicates present in the matrix the stackoverflow occurs.

Kind regards!

Hello!

Thanks for your report! This issue was confirmed http://bugs.alglib.net/view.php?id=521 and fixed in the development version of ALGLIB. We are going to make new release very soon, somewhere in the first days of June. Meanwhile you may manually apply fix to your version of ALGLIB.

Attachment contains small patch of C# code. You should replace kdtreegeneratetreerec function from alglibmisc.cs by this patch. Please, confirm that it worked for you. And thanks for the report again!

All-right, thank you a million times!
I'm using this for testing of some theoretical texture synthesis algorithms for my master thesis, I couldn't be more thankful for your quick response as deadlines are approaching soon.
I've just built a new dll, after applying your fix, and tested it on the same scenario that gave me errors, but now it works perfectly!

Keep up the good work!
Kind regards!
Jeremy