Methods and apparatuses are provided for storing graph data within a column-oriented data store. Graph data including vertex data describing one or more vertices in the graph and edge data describing one or more edges within the graph may be received. One or more vertex rows within the column-oriented data store may be assigned, whereby each vertex row of the one or more vertex rows is assigned to one vertex of the one or more vertices. One or more edge rows within the column-oriented data store may also be assigned, whereby each edge row of the one or more edge rows is assigned to one edge of the one or more edges. At least one vertex row and at least one edge row may be populated based on the graph data.