search

metatron-app / metatron-discovery

Powerful & Easy way for big data discovery
https://metatron.app
Apache License 2.0
442 stars 112 forks source link

Extend range of b parameter of HLL to 24 #3945

Open navis opened 2 years ago

navis commented 2 years ago

was up to 16, which is 32K

------------- 10,000
11 --> (0:2032::0:0) -2.400 % (1 KB) 
12 --> (0:3736::0:0) 0.399 % (2 KB) 
13 --> (0:5753::0:0) 0.748 % (4 KB) 
14 --> (0:7498::0:0) -0.242 % (8 KB) 
15 --> (0:8625::0:0) -0.092 % (16 KB) 
16 --> (0:9253::0:0) 0.250 % (25 KB) 
17 --> (0:9635::0:0) -0.075 % (27 KB) 
18 --> (0:9803::0:0) 0.090 % (28 KB) 
19 --> (0:9894::0:0) 0.115 % (28 KB) 
20 --> (0:9946::0:0) 0.065 % (29 KB) 
21 --> (0:9977::0:0) -0.008 % (29 KB) 
22 --> (0:9991::0:0) -0.029 % (29 KB) 
23 --> (0:9996::0:0) -0.020 % (29 KB) 
24 --> (0:10000::0:0) -0.030 % (29 KB) 
------------- 100,000
11 --> (3:2042::1472:17) -2.400 % (1 KB) 
12 --> (1:4095::3520:17) -0.352 % (2 KB) 
13 --> (1:8173::7616:17) 1.696 % (4 KB) 
14 --> (0:16351::7616:17) 1.696 % (8 KB) 
15 --> (0:31179::7616:17) -0.352 % (16 KB) 
16 --> (0:51311::40384:17) -0.113 % (32 KB) 
17 --> (0:70162::40384:17) -0.447 % (64 KB) 
18 --> (0:83115::40384:17) 0.031 % (128 KB) 
19 --> (0:91069::40384:17) -0.034 % (243 KB) 
20 --> (0:95338::40384:17) 0.045 % (266 KB) 
21 --> (0:97587::40384:17) 0.068 % (279 KB) 
22 --> (0:98765::2137536:17) 0.053 % (285 KB) 
23 --> (0:99363::6331840:17) 0.043 % (289 KB) 
24 --> (0:99686::6331840:17) 0.016 % (291 KB) 
------------- 1,000,000
11 --> (7:1997::1472:17) 3.130 % (1 KB) 
12 --> (5:4093::3793:21) 1.901 % (2 KB) 
13 --> (4:8189::7889:21) 0.672 % (4 KB) 
14 --> (3:16371::7889:21) 0.672 % (8 KB) 
15 --> (2:32756::24273:21) 0.262 % (16 KB) 
16 --> (1:65507::57041:21) -0.352 % (32 KB) 
17 --> (0:130998::122577:21) 0.058 % (64 KB) 
18 --> (0:256427::253649:21) -0.352 % (128 KB) 
19 --> (0:446553::515793:21) -0.072 % (256 KB) 
20 --> (0:644748::515793:21) -0.055 % (512 KB) 
21 --> (0:795225::1564369:21) 0.021 % (1024 KB) 
22 --> (0:889646::3661521:21) 0.010 % (2328 KB) 
23 --> (0:942787::7855825:21) -0.010 % (2605 KB) 
24 --> (0:970872::7855825:21) -0.010 % (2761 KB) 
------------- 10,000,000
11 --> (10:2031::1539:24) 1.000 % (1 KB) 
12 --> (9:4063::3587:24) -0.413 % (2 KB) 
13 --> (7:8191::3587:24) -0.680 % (4 KB) 
14 --> (6:16383::3587:24) -0.475 % (8 KB) 
15 --> (5:32765::19971:24) -0.495 % (16 KB) 
16 --> (4:65530::52739:24) -0.106 % (32 KB) 
17 --> (3:131060::118275:24) 0.078 % (64 KB) 
18 --> (2:262129::249347:24) 0.344 % (128 KB) 
19 --> (1:524256::511491:24) 0.037 % (256 KB) 
20 --> (0:1048499::1035779:24) 0.058 % (512 KB) 
21 --> (0:2079287::1035779:24) 0.037 % (1024 KB) 
22 --> (0:3807746::1035779:24) -0.001 % (2048 KB) 
23 --> (0:5841252::5230083:24) 0.023 % (4096 KB) 
24 --> (0:7532728::13618691:24) 0.009 % (8192 KB)
navis commented 2 years ago

Changed to use 64bit hash and fixed high correction condition

------------- 10,000
11 --> (0::0:2031) 0.079% (1 KB, 15 msec)
12 --> (0::0:3726) -2.836% (2 KB, 3 msec)
13 --> (0::0:5771) 0.141% (4 KB, 2 msec)
14 --> (0::0:7426) 1.080% (8 KB, 1 msec)
15 --> (0::0:8568) 0.680% (16 KB, 2 msec)
16 --> (0::0:9218) 0.657% (25 KB, 5 msec)
17 --> (0::0:9582) 0.497% (27 KB, 7 msec)
18 --> (0::0:9790) 0.225% (28 KB, 5 msec)
19 --> (0::0:9893) 0.125% (28 KB, 8 msec)
20 --> (0::0:9952) 0.005% (29 KB, 5 msec)
21 --> (0::0:9971) 0.052% (29 KB, 4 msec)
22 --> (0::0:9982) 0.061% (29 KB, 7 msec)
23 --> (0::0:9992) 0.020% (29 KB, 11 msec)
24 --> (0::0:9998) -0.010% (29 KB, 26 msec)
------------- 100,000
11 --> (21::3:2042) 5.741% (1 KB, 10 msec)
12 --> (21::2:4088) 2.618% (2 KB, 6 msec)
13 --> (21::1:8177) 0.897% (4 KB, 6 msec)
14 --> (21::0:16351) 0.014% (8 KB, 5 msec)
15 --> (21::0:31189) -0.755% (16 KB, 5 msec)
16 --> (21::0:51291) -0.025% (32 KB, 7 msec)
17 --> (21::0:69854) 0.212% (64 KB, 6 msec)
18 --> (21::0:83054) 0.120% (128 KB, 7 msec)
19 --> (21::0:90951) 0.109% (243 KB, 8 msec)
20 --> (21::0:95428) -0.054% (266 KB, 9 msec)
21 --> (21::0:97726) -0.077% (279 KB, 11 msec)
22 --> (21::0:98887) -0.072% (286 KB, 13 msec)
23 --> (21::0:99426) -0.021% (289 KB, 21 msec)
24 --> (21::0:99710) -0.008% (291 KB, 36 msec)
------------- 1,000,000
11 --> (21::7:2010) -3.945% (1 KB, 51 msec)
12 --> (21::5:4094) -2.273% (2 KB, 50 msec)
13 --> (21::4:8187) -1.055% (4 KB, 56 msec)
14 --> (21::3:16377) -0.737% (8 KB, 65 msec)
15 --> (21::2:32751) -0.034% (16 KB, 64 msec)
16 --> (21::1:65512) -0.457% (32 KB, 54 msec)
17 --> (21::0:131006) -0.146% (64 KB, 56 msec)
18 --> (21::0:256283) -0.190% (128 KB, 59 msec)
19 --> (21::0:446138) 0.206% (256 KB, 65 msec)
20 --> (21::0:644598) -0.016% (512 KB, 89 msec)
21 --> (21::0:795431) -0.012% (1024 KB, 92 msec)
22 --> (21::0:889878) -0.019% (2330 KB, 94 msec)
23 --> (21::0:942558) 0.015% (2606 KB, 120 msec)
24 --> (21::0:970721) 0.006% (2762 KB, 146 msec)
------------- 10,000,000
11 --> (23::9:2047) -0.381% (1 KB, 528 msec)
12 --> (23::9:4058) -0.564% (2 KB, 482 msec)
13 --> (23::8:8120) 0.047% (4 KB, 493 msec)
14 --> (23::7:16257) 0.291% (8 KB, 476 msec)
15 --> (23::6:32487) 0.323% (16 KB, 505 msec)
16 --> (23::4:65529) 0.199% (32 KB, 505 msec)
17 --> (23::3:131068) -0.138% (64 KB, 388 msec)
18 --> (23::2:262114) -0.018% (128 KB, 452 msec)
19 --> (23::1:524251) -0.152% (256 KB, 460 msec)
20 --> (23::0:1048514) -0.251% (512 KB, 528 msec)
21 --> (23::0:2079747) -0.209% (1024 KB, 615 msec)
22 --> (23::0:3807900) -0.017% (2048 KB, 651 msec)
23 --> (23::0:5842699) -0.025% (4096 KB, 761 msec)
24 --> (23::0:7534613) -0.025% (8192 KB, 988 msec)
navis commented 2 years ago 
------------- 1,000,000,000
11 --> (32::16:2046) -0.881% (1 KB, 47354 msec)
12 --> (32::15:4092) 1.553% (2 KB, 48883 msec)
13 --> (32::14:8183) -0.060% (4 KB, 36086 msec)
14 --> (32::13:16375) -0.533% (8 KB, 37516 msec)
15 --> (32::12:32745) -0.096% (16 KB, 36766 msec)
16 --> (32::11:65503) -0.221% (32 KB, 36616 msec)
17 --> (32::10:131002) 0.074% (64 KB, 35668 msec)
18 --> (32::9:261997) 0.186% (128 KB, 48117 msec)
19 --> (32::7:524287) -0.037% (256 KB, 36993 msec)
20 --> (32::6:1048575) 0.008% (512 KB, 39084 msec)
21 --> (32::5:2097151) 0.151% (1024 KB, 39946 msec)
22 --> (32::4:4194303) 0.125% (2048 KB, 44407 msec)
23 --> (32::3:8388607) 0.096% (4096 KB, 53969 msec)
24 --> (32::2:16777211) 0.095% (8192 KB, 75986 msec)