The disclosed embodiments provide a system that manages access to data. During operation, the system provides a graph-based data model of the data, wherein the graph-based model comprises a set of nodes and a set of directed edges among the nodes. Next, the system stores the graph-based data model in a set of partitions, wherein each partition from the set of partitions includes one or more nodes from the set of nodes and all outgoing edges from the one or more nodes. Finally, the system enables lookup of a set of outgoing edges associated with a source node from the one or more nodes.