Skip to content

Hashxor bucket repetitions

kennyzzhang edited this page Apr 26, 2021 · 12 revisions

Lab machine: Repeat 1000 times, 1 million updates

Sketch size Normal repetitions Half repetitions Quarter repetitions
10^1 10 failures, 82.0521 seconds 90 failures, 65.0393 seconds 289 failures, 52.0094 seconds
10^2 1 failure, 133.213 seconds 30 failures, 81.9698 seconds 304 failures, 54.664 seconds
10^3 1 failure, 188.457 seconds 6 failures, 116.514 seconds 99 failures, 71.2486 seconds
10^4 248.76 seconds 148.883 seconds 23 failures, 86.28 seconds
10^5 291.848 seconds 163.202 seconds 7 failures, 101.099 seconds
10^6 334.589 seconds 191.865 seconds 5 failures, 119.78 seconds
10^7 391.6 seconds 220.536 seconds 135.314 seconds
10^8 454.643 seconds 245.54 seconds 1 failure, 140.928 seconds
10^9 498.487 seconds 274.692 seconds 155.656 seconds
10^10 559.091 seconds 292.141 seconds 162.996 seconds
10^11 577.927 seconds 306.222 seconds 177.668 seconds
10^12 620.079 seconds 334.595 seconds 191.757 seconds
10^13 677.144 seconds 363.248 seconds 206.288 seconds
10^14 720.308 seconds 377.375 seconds 206.355 seconds
10^15 766.071 seconds 406.258 seconds 220.63 seconds
10^16 820.063 seconds 434.391 seconds 234.629 seconds
10^17 862.332 seconds 449.42 seconds 249.062 seconds
10^18 905.662 seconds 477.475 seconds 262.806 seconds

Graph testing: Lab machine: repeat 1000 times

Nodes in graph Edge updates Normal repetitions Half repetitions Quarter repetitions
10 1 0.00158809 seconds 0.000961117 seconds 0.000820329 seconds
31 23 0.0350829 seconds 0.0217669 seconds 1000 failures, 0.0144823 seconds
100 293 0.712662 seconds 0.423857 seconds 248 failures, 0.2499 seconds
316 2979 12.161 seconds 6.45604 seconds 1000 failures, 4.03104 seconds
1000 29963 320.54 seconds 7 failures, 136.748 seconds 933 failures, 60.6819 seconds
3162 299844 5893.79 seconds 1 failure, 2995.66 seconds 922 failures, 1554.74 seconds

Continuous Sketch testing: lab machine, 1000 updates between samples, 1000000 samples.

Sketch size Normal repetitions Half repetitions Quarter repetitions
10^1 31239 76477 75759
10^2 31 59519 326748
10^3 4 663 45139
10^4 0 261 8802
10^5 0 36 11601
10^6 0 0 141
10^7 0 0 0
10^8 0 0 0
10^9 0 0 0
10^10 0 0 0

Continuous graph testing: 1000 updates between samples, 1000 samples

Graph size Normal repetitions Half repetitions Quarter repetitions
100 0 41 954
316 0 42 945
1000 0 0 963
3162 0 0 907
10000 0 0 997