Information Technology Reference
In-Depth Information
900
800
700
600
500
400
300
200
Complete History
Granularity 20 000 ev.
Granularity 50 000 ev.
Granularity 100 000 ev.
100
0
0
2000
4000
6000
8000
10000
12000
Size of the orignal trace (MB)
Fig. 9.
History tree construction time
Comparison with R-Tree:
To compare the construction time of the proposed
method against a R-Tree, we use a main memory implementation of a R-Tree.
Figure 10 shows the construction time comparison of two methods. As mentioned
earlier, the R-Tree is very slow because it requires lots of re-balancing. The
comparison proves the e
ciency of our method for the incrementally arriving
data.
350
Complete History
In−memory R−Tree
300
250
200
150
100
50
0
0
100
200
300
400
500
600
700
Size of the orignal trace (MB)
Fig. 10.
Comparing the construction time with the R-Tree method
5.2 Storage Space
Figure 11 compares the storage required in 4 cases: the case that updates the
database completely for each single state change, and the cases that update
the database partially, for each 20,000, 50,000, 100,000 events, respectively. As
mentioned earlier, updating the history database for every single state change is
a costly operation and requires more storage space.
