A method and system are provided. The method includes storing, in a memory, temporal data for a temporal graph. The memory includes a temporal graph storage structure having a set of buckets. The temporal data stored in the buckets includes respective data segments implemented using graph edges. Each of the graph edges has a start time and an end time associated therewith. The method further includes the methods, performed by a processor, of: forming an index that categorizes the graph edges based on the end times of the graph edges; positioning the graph edges within respective ones of the buckets for storage using the index such that the graph edges are positioned in the respective ones of the buckets in a chronological order that is based on the end times; and accessing the temporal graph storage structure using the index responsive to a temporal graph query.