Amazon.com, Inc.
Scalable graph authoring and versioning techniques

Abstract:

System and methods are maintaining various versions of a graph (e.g., a geometric graph) by a graph management engine. A graph may be partitioned into a number of cells (e.g., utilizing a spatial projection formula). Each cell may be associated with graph data such as nodes and/or edges that are located within the area defined by the boundaries of a cell. The graph management engine may process modifications to the graph. Upon determining that a modification is to be made to a cell, the graph management engine may generate a new cell to contain the previous cell content as modified. The new cell may be assigned a new cell identifier, and a version map corresponding to current cell version identifiers may be maintained. Subsequent data requests for graph data may be processed utilizing the version map to ensure that current graph data is provided in response to the request.