Uber Technologies, Inc.
COMPARING MAP BUILDS USING HIERARCHICAL TREE REPRESENTATIONS

Abstract:

A computing system uses tree data structures summarizing map builds to identify differences between map builds. The tree data structures include nodes summarizing portions of geographic regions of map builds. Responsive to a request to compare a first and second map build, the computing system accesses the tree data structures for the first and second map builds and identifies differences by traversing the tree data structures in lockstep and comparing the hash values for corresponding nodes in the tree data structures. The computing system traverses the tree data structures by identifying nodes that are different between the tree data structures until one or more bottom-level nodes are identified as different. The computing system identifies map features corresponding to the identified bottom-level nodes as different and transmits the identified map features to a client device associated with the request.