Introduction
Terminology and notation
Graphs and adjacency lists
Dynamic graphs
Analysis of dynamic graphs
Representing a dynamic graph in memory
Problem definition
Compile-time selection of efficient data structures
Compile-time approach
Benchmarking
-
f 1(x)=a+b·x+c·x 2
-
f 2(x)=a+b·l o g(x)
Instrumentation, execution, and profiling
Analysis and re-compilation
Benchmarking results
t
|
d
|
\(e_{d,t,get_{s}}(x)\)
|
\(e_{d,t,get_{f}}(x)\)
|
---|---|---|---|
v
| A | 23.74+0.91·x−0.01·x
2
| 16.72+0.15·x−0.00·x
2
|
AL | 24.49+1.41·x−0.01·x
2
| 41.09+1.82·x+0.04·x
2
| |
HAL | 47.58+0.18·x−0.00·x
2
| 60.36+3.23·x−0.00·x
2
| |
HM | 73.57+0.93·x−0.00·x
2
| 57.48+15.46·l
o
g(x) | |
HS | 56.20+40.23·x−0.18·x
2
| 54.05+40.99·x−0.17·x
2
| |
HT | 153.87+18.14·l
o
g(x) | 98.70+19.96·l
o
g(x) | |
LL | 39.80+0.24·x−0.00·x
2
| 26.28+14.04·x+0.22·x
2
| |
e
| A | 22.92+1.88·x+0.02·x
2
| 27.78+1.51·x+0.02·x
2
|
AL | 23.49+3.65·x−0.00·x
2
| 29.81+3.63·x−0.00·x
2
| |
HAL | 51.42+5.26·x−0.02·x
2
| 53.08+4.77·x−0.02·x
2
| |
HM | 371.51+1.38·x−0.00·x
2
| 357.04+1.44·x−0.00·x
2
| |
HS | 33.45+15.87·x−0.04·x
2
| 69.20+34.08·x+0.01·x
2
| |
HT | 442.95+2.09·x−0.01·x
2
| 407.83+5.01·x−0.04·x
2
| |
LL | 31.36+11.18·x+0.10·x
2
| 35.44+10.59·x+0.11·x
2
|
o
|
v
|
e
| ||||||||
---|---|---|---|---|---|---|---|---|---|---|
101
| 102
| 103
| 104
| 105
| 101
| 102
| 103
| 104
| 105
| |
init
| LL | LL | LL | LL | LL | LL | LL | LL | LL | LL |
a
d
d
s
| AL | HS | HAL | HAL | HS | AL | AL | HS | HT | HT |
a
d
d
f
| A | A | A | HS | A | A | HS | HS | HS | HS |
r
e
m
s
| A | A | A | A | A | A | A | HS | HM | HM |
r
e
m
f
| A | A | A | A | A | AL | HS | HS | HS | HM |
g
e
t
s
| A | LL | A | A | LL | A | HAL | LL | HM | HT |
g
e
t
f
| A | A | A | A | A | A | HAL | LL | HM | HM |
iter
| AL | HAL | HAL | HAL | LL | AL | HAL | LL | LL | A |
rand
| A | HAL | A | A | A | AL | HAL | A | A | HAL |
size
| A | LL | A | A | A | A | A | A | A | HAL |
c
o
n
t
s
| A | A | A | A | LL | A | HS | HS | HAL | HS |
c
o
n
t
f
| A | A | A | A | HS | A | HS | LL | HM | HS |
Profiling results
Evaluation
Datasets
Constant workload
Metric | Constant workload (MD) | Non-constant workload (FB) | ||||
---|---|---|---|---|---|---|
V |
E
|
adj
|
V
|
E
|
adj
| |
All-pairs shortest paths | A | HM | AL | HAL | HAL | LL |
Assortativity | A | HM | A | HAL | HAL | A |
Betweenness centrality | HAL | HM | AL | LL | HAL | LL |
Clustering coefficient | A | HM | A | HAL | HAL | AL |
Degree distribution | A | HM | A | HAL | HAL | AL |
Rich-club connectivity | A | HM | AL | HAL | HAL | AL |
Connected components | A | HM | AL | HAL | HAL | AL |
Non-constant workload
Summary of the compile-time approach
Run-time selection of efficient data structures
Run-time approach
Performance analysis
list size | cont:V | get:V | iter:V | add:V | cont:E | get:E | iter:E | add:E |
---|---|---|---|---|---|---|---|---|
10k
|
A
|
A
|
AL
|
HS
|
HAL
|
HM
|
AL
|
HS
|
20k
|
A
|
A
|
AL
|
HS
|
HS
|
HM
|
AL
|
HS, HM
|
30k
|
A
|
A
|
AL
|
HS
|
HS
|
HM
|
A
|
HM
|
40k
|
A
|
A
|
AL
|
HS
|
HS
|
HM
|
A
|
HM
|