Efficient data structures for dynamic graph analysis - Technical. Report. Benjamin Schiller1, Clemens Deusser1, Jeronimo
Efficient data structures for dynamic graph analysis - Technical Report Benjamin Schiller1 , Clemens Deusser1 , Jeronimo Castrillon2 , and Thorsten Strufe1 1
Privacy and Data Security, Department of Computer Science, TU Dresden
[email protected],
[email protected] 2 Compiler Construction, Department of Computer Science, TU Dresden
[email protected]
Table of Contents
Efficient data structures for dynamic graph analysis - Technical Report . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Benjamin Schiller, Jeronimo Castrillon, Thorsten Strufe 1 Measurements and estimation functions for s =∈ [1, 100] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Node - 100 - 10000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Edge - 100 - 10000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Node - 100 - 100000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Edge - 100 - 100000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Node - 100 - 200000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 Edge - 100 - 200000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Measurements and estimation functions for s =∈ [1, 1000] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Node - 1000 - 1000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Edge - 1000 - 1000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Node - 1000 - 10000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Edge - 1000 - 10000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Measurements and estimation functions for s =∈ [1, 10000] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Node - 10000 - 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Edge - 10000 - 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Node - 10000 - 100 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Edge - 10000 - 100 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Measurements and estimation functions for s =∈ [1, 50000] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Node - 50000 - 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Edge - 50000 - 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Resulting functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Functions - Node . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Functions - Edge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 3 3 4 5 6 7 8 9 9 10 11 12 13 13 14 15 16 17 17 18 19 19 20
1 1.1
Measurements and estimation functions for s =∈ [1, 100] Node - 100 - 10000
(a) addf
(b) adds
(c) init
(d) remf
(e) rems
(f) iter
(g) getf
(h) gets
(i) rand
(j) contf
(k) conts
(l) size
Fig. 1. Runtime estimations ed,v,o for list sizes s ∈ [1, 100] (measured for 10000 list instances)
1.2
Edge - 100 - 10000
(a) addf
(b) adds
(c) init
(d) remf
(e) rems
(f) iter
(g) getf
(h) gets
(i) rand
(j) contf
(k) conts
(l) size
Fig. 2. Runtime estimations ed,e,o for list sizes s ∈ [1, 100] (measured for 10000 list instances)
1.3
Node - 100 - 100000
(a) addf
(b) adds
(c) init
(d) remf
(e) rems
(f) iter
(g) getf
(h) gets
(i) rand
(j) contf
(k) conts
(l) size
Fig. 3. Runtime estimations ed,v,o for list sizes s ∈ [1, 100] (measured for 100000 list instances)
1.4
Edge - 100 - 100000
(a) addf
(b) adds
(c) init
(d) remf
(e) rems
(f) iter
(g) getf
(h) gets
(i) rand
(j) contf
(k) conts
(l) size
Fig. 4. Runtime estimations ed,e,o for list sizes s ∈ [1, 100] (measured for 100000 list instances)
1.5
Node - 100 - 200000
(a) addf
(b) adds
(c) init
(d) remf
(e) rems
(f) iter
(g) getf
(h) gets
(i) rand
(j) contf
(k) conts
(l) size
Fig. 5. Runtime estimations ed,v,o for list sizes s ∈ [1, 100] (measured for 200000 list instances)
1.6
Edge - 100 - 200000
(a) addf
(b) adds
(c) init
(d) remf
(e) rems
(f) iter
(g) getf
(h) gets
(i) rand
(j) contf
(k) conts
(l) size
Fig. 6. Runtime estimations ed,e,o for list sizes s ∈ [1, 100] (measured for 200000 list instances)
2 2.1
Measurements and estimation functions for s =∈ [1, 1000] Node - 1000 - 1000
(a) addf
(b) adds
(c) init
(d) remf
(e) rems
(f) iter
(g) getf
(h) gets
(i) rand
(j) contf
(k) conts
(l) size
Fig. 7. Runtime estimations ed,v,o for list sizes s ∈ [1, 1000] (measured for 1000 list instances)
2.2
Edge - 1000 - 1000
(a) addf
(b) adds
(c) init
(d) remf
(e) rems
(f) iter
(g) getf
(h) gets
(i) rand
(j) contf
(k) conts
(l) size
Fig. 8. Runtime estimations ed,e,o for list sizes s ∈ [1, 1000] (measured for 1000 list instances)
2.3
Node - 1000 - 10000
(a) addf
(b) adds
(c) init
(d) remf
(e) rems
(f) iter
(g) getf
(h) gets
(i) rand
(j) contf
(k) conts
(l) size
Fig. 9. Runtime estimations ed,v,o for list sizes s ∈ [1, 1000] (measured for 10000 list instances)
2.4
Edge - 1000 - 10000
(a) addf
(b) adds
(c) init
(d) remf
(e) rems
(f) iter
(g) getf
(h) gets
(i) rand
(j) contf
(k) conts
(l) size
Fig. 10. Runtime estimations ed,e,o for list sizes s ∈ [1, 1000] (measured for 10000 list instances)
3 3.1
Measurements and estimation functions for s =∈ [1, 10000] Node - 10000 - 10
(a) addf
(b) adds
(c) init
(d) remf
(e) rems
(f) iter
(g) getf
(h) gets
(i) rand
(j) contf
(k) conts
(l) size
Fig. 11. Runtime estimations ed,v,o for list sizes s ∈ [1, 10000] (measured for 10 list instances)
3.2
Edge - 10000 - 10
(a) addf
(b) adds
(c) init
(d) remf
(e) rems
(f) iter
(g) getf
(h) gets
(i) rand
(j) contf
(k) conts
(l) size
Fig. 12. Runtime estimations ed,e,o for list sizes s ∈ [1, 10000] (measured for 10 list instances)
3.3
Node - 10000 - 100
(a) addf
(b) adds
(c) init
(d) remf
(e) rems
(f) iter
(g) getf
(h) gets
(i) rand
(j) contf
(k) conts
(l) size
Fig. 13. Runtime estimations ed,v,o for list sizes s ∈ [1, 10000] (measured for 100 list instances)
3.4
Edge - 10000 - 100
(a) addf
(b) adds
(c) init
(d) remf
(e) rems
(f) iter
(g) getf
(h) gets
(i) rand
(j) contf
(k) conts
(l) size
Fig. 14. Runtime estimations ed,e,o for list sizes s ∈ [1, 10000] (measured for 100 list instances)
4 4.1
Measurements and estimation functions for s =∈ [1, 50000] Node - 50000 - 1
(a) addf
(b) adds
(c) init
(d) remf
(e) rems
(f) iter
(g) getf
(h) gets
(i) rand
(j) contf
(k) conts
(l) size
Fig. 15. Runtime estimations ed,v,o for list sizes s ∈ [1, 50000] (measured for 1 list instances)
4.2
Edge - 50000 - 1
(a) addf
(b) adds
(c) init
(d) remf
(e) rems
(f) iter
(g) getf
(h) gets
(i) rand
(j) contf
(k) conts
(l) size
Fig. 16. Runtime estimations ed,e,o for list sizes s ∈ [1, 50000] (measured for 1 list instances)
5 5.1
Resulting functions Functions - Node
(a) addf
(b) adds
(c) init
(d) remf
(e) rems
(f) iter
(g) getf
(h) gets
(i) rand
(j) contf
(k) conts
(l) size
Fig. 17. Runtime estimations ed,v,o
5.2
Functions - Edge
(a) addf
(b) adds
(c) init
(d) remf
(e) rems
(f) iter
(g) getf
(h) gets
(i) rand
(j) contf
(k) conts
(l) size
Fig. 18. Runtime estimations ed,e,o
