The people are living in an ever more connected world, where data recording the interactions between people, software systems, and the physical world is becoming increasingly prevalent. This data often takes the form of a temporally evolving graph, where entities are the vertices and the interactions between them are the edges. The authors call such graphs interaction graphs. Various application domains, including telecommunications, transportation, and social media, depend on analytics performed on interaction graphs. The ability to efficiently support historical analysis over interaction graphs requires effective solutions for the problem of data layout on disk.