Modeling graphs on distributed storage

Abstract

In one aspect, a method for modeling graphs on distributed storage, comprising: receiving graph data including vertices, edges, and properties; mapping each vertex to a vertex record in a distributed storage system; mapping each edge to an edge record in the distributed storage system; mapping each property to a property record in the distributed storage system; determining, for each vertex, whether a number of incident edges exceeds a maximum record size threshold; storing pointers to incident edge records directly within vertex records when the number of incident edges does not exceed the maximum record size threshold; utilizing an adjacency index to lookup incident edge records when the number of incident edges exceeds the maximum record size threshold; and executing graph traversal operations that navigate from vertex to vertex by accessing the appropriate edge records through either the stored pointers or the adjacency index.

What is claimed by United States patent: 
     
         1 . A method for modeling graphs on distributed storage, comprising:
 receiving graph data including vertices, edges, and properties;   mapping each vertex to a vertex record in a distributed storage system; mapping each edge to an edge record in the distributed storage system;   mapping each property to a property record in the distributed storage system;   determining, for each vertex, whether a number of incident edges exceeds a maximum record size threshold;   storing pointers to incident edge records directly within vertex records when the number of incident edges does not exceed the maximum record size threshold;   utilizing an adjacency index to look up incident edge records when the number of incident edges exceeds the maximum record size threshold; and   executing graph traversal operations that navigate from vertex to vertex by accessing the appropriate edge records through either the stored pointers or the adjacency index.   
     
     
         2 . The method of  claim 1 , further comprising:
 collocating property records with their associated vertex or edge records to improve data locality during traversal operations.   
     
     
         3 . The method of  claim 1 , further comprising:
 implementing a multi-level caching system to store frequently accessed vertex and edge records to reduce the number of read operations to the distributed storage system.   
     
     
         4 . The method of  claim 1 , further comprising:
 packing partial edge information into vertex records to the extent available space permits within the maximum record size threshold.   
     
     
         5 . The method of  claim 1 , wherein executing graph traversal operations further comprises:
 creating execution pointers at starting elements;   moving the execution pointers to adjacent elements based on traversal logic;   forking execution pointers when multiple adjacent elements match traversal criteria;
 and aggregating results from multiple execution pointers to produce a final query result. 
   
     
     
         6 . The method of  claim 1 , further comprising:
 performing batch operations against the distributed storage system to retrieve groups of related elements required for query execution.   
     
     
         7 . The method of  claim 1 , further comprising:
 implementing a tree-structured record pattern for vertices with high edge counts, comprising a primary vertex record and multiple leaf records containing additional edge pointers.   
     
     
         8 . The method of  claim 1 , wherein each edge record contains pointers to exactly two vertex records, and each vertex record contains pointers to zero or more edge records based on the maximum record size threshold. 
     
     
         9 . The method of  claim 1 , wherein executing graph traversal operations includes utilizing a graph traversal runtime compatible with the TinkerPop framework and Gremlin query language. 
     
     
         10 . The method of  claim 1 , further comprising:
 dynamically selecting between direct pointer access, adjacency index lookup, or edge set scanning based on vertex degree and system configuration to optimize traversal performance.