EffiCuts: endless cutting

[Nic30]

Hello,

for some larger rulesets the reference EffiCuts implementations ends with an error acl1_seed_10K.zip

Error: [Tree 0] more that 100 levels!

https://github.com/acsl-technion/nuevomatch/blob/master/vendor/efficuts.cpp#L1324

I believe that this caused by a missing part of the CalcEquiCuts2D function and it is probably related to a todo https://github.com/acsl-technion/nuevomatch/blob/master/vendor/efficuts.cpp#L893.

What happens is that all rules of parent node are added to child[0]. Here is my simple debug printf, increasing MAX_ALLOWED_LEVELS won't help.

....
>>>>>>>>>>>>>>>>cutting (rule dump):
1 2499805184:2516582399 0:4294967295 0:65535 0:65535 0:255 
5 2499805184:2516582399 0:4294967295 0:65535 0:65535 1:1 
7 2499805184:2516582399 0:4294967295 0:65535 0:65535 6:6 
8 2511275520:2511276031 0:4294967295 0:65535 0:65535 0:255 
10 2511275520:2511276031 0:2147483647 0:65535 0:65535 0:255 
23 2511275520:2511276031 0:4294967295 0:65535 0:65535 1:1 
25 2511275520:2511276031 0:4294967295 0:65535 0:65535 6:6 
26 2511275520:2511276031 0:2147483647 0:65535 0:65535 6:6 
29 2511275871:2511275871 0:1073741823 0:65535 0:65535 0:255 
64 2511275871:2511275871 0:1073741823 0:65535 0:65535 6:6 
cut dim:0, 1
BestSplitPoint:2511275871, 1073741823

>>>>>>>>>>>>>>>>cutting:
1 2499805184:2516582399 0:4294967295 0:65535 0:65535 0:255 
5 2499805184:2516582399 0:4294967295 0:65535 0:65535 1:1 
7 2499805184:2516582399 0:4294967295 0:65535 0:65535 6:6 
8 2511275520:2511276031 0:4294967295 0:65535 0:65535 0:255 
10 2511275520:2511276031 0:2147483647 0:65535 0:65535 0:255 
23 2511275520:2511276031 0:4294967295 0:65535 0:65535 1:1 
25 2511275520:2511276031 0:4294967295 0:65535 0:65535 6:6 
26 2511275520:2511276031 0:2147483647 0:65535 0:65535 6:6 
29 2511275871:2511275871 0:1073741823 0:65535 0:65535 0:255 
64 2511275871:2511275871 0:1073741823 0:65535 0:65535 6:6 
cut dim:0, 1
BestSplitPoint:2511275871, 1073741823

Error: [Tree 0] more that 100 levels!

Do you know how to fix this issue? Or do you at least remember what the mentioned todo mean so I can fix it myself?

[alonrs]

Hi @Nic30

Does this problem also appear using the original EffiCuts code? (here) If not, try switching fineOn parameter to zero (here)

Hope this helps

[Nic30]

Sorry for long delay.

Does this problem also appear using the original EffiCuts code? (here)

yes it does

./compressedcuts -b16 -s8 -f7 -r acl1_seed_10K -m1 -c1 -n0.5 -i0.05 -t0 -u0 -g1 -z1
******************************************
Bucket Size =  16
Space Factor = 8.000000
bin = 0.500000
IPbin = 0.050000
hypercuts = 1
Num_Rules_Moved_Up = 0
compressionON = 1
binningON = 1
mergingON = 1
num_intervals = 7
******************************************
number of rules read from file = 2143
Cutoffs[0] = 1778
Cutoffs[1] = 214
Cutoffs[2] = 85
Cutoffs[3] = 42
Cutoffs[4] = 21
Number of trees before merge: 7
Number of trees after merge: 4
Incoming No of Rules in this tree = 36
Incoming No of Rules in this tree = 4
Incoming No of Rules in this tree = 260
Incoming No of Rules in this tree = 1843
Warning: parent and child are identical with 1313 rules!
Error: This problematic node has 1313 rules!

If not, try switching fineOn parameter to zero (here)

fineOn = 0

Won't help.

I guess that I have to read the original paper to figure out how it was supposed to work in this corner case. I think that there is just some missing part of condition or < <= mismatch somewhere in mentioned part of the code. If anyone have any guess I would be happy.

[vamsiDT]

I had a similar error with a classbench ruleset generated using fw1_seed

I am curious why this is happening. I tried with the original efficuts implementation too. @Nic30 In your previous example, using the original efficuts repository, can you try to remove the exit(1) line after printf(Error: This problematic node has... or increase TOO_MUCH to a reasonably large value?

I am curious if the error still pops up.

If the error doesn't pop up after removing exit(1) line, is the output consistent?

[Nic30]

@vamsiDT the amount of rule fragments in node is not decreasing in the process, removing the fail-safe won't help. The issue is probably mentioned range comparison. In my test case I am using rulesets of 5K to 1M rules (classbench-ng, real, generated from some openstack app etc.) the problem in my case is that there is no rulesets with 50K rules or larger which actually works.