System and method for graph conditioning with non-overlapping orderable values for efficient graph evaluation

摘要

Embodiments may include transforming a subgraph into a new subgraph such that, for a given logical operation of the new subgraph, more primitives are grouped under that logical operation relative to the original subgraph. Each primitive may represent a range of values. The primitives of a given logical operation of the transformed subgraph may represent values that overlap. Embodiments may include performing a union operation on the primitives of the given logical operation of the transformed subgraph to generate an ordered set of non-overlapping values. Embodiments may include replacing the given logical operation of the transformed subgraph with information specifying that set. In embodiments, dependent on the given logical operation's complexity, the requisite time to perform a search operation for a value within the ordered set of non-overlapping values is less than the requisite time to perform the given logical operation on its respective primitives.

主权项

1. A computer-implemented method, comprising:
performing one or more transformations on a subgraph comprising logical operations and associated primitives of one or more classes, wherein respective primitives of the common class represents respective geographic regions, to generate a second logically equivalent subgraph that also includes logical operations and associated primitives, wherein the one or more transformations are performed such that, for a given logical operation of the second subgraph, a partially-ordered plurality of child primitives of a common class are transformed into a logically-equivalent totally-ordered set of non-overlapping geographic regions, wherein the one or more transformations comprises:
transforming the logical operation of the partially-ordered plurality of geographic regions of a common class into a logically-equivalent partially-ordered set of the plurality of geographic regions, wherein at least two of the geographic regions overlap,transforming the partially-ordered set of the plurality of geographic regions into a logically-equivalent plurality of sets, where a given set of the plurality of sets is a set of a separate geographic region of the plurality of geographic regions and at least two sets comprise overlapping geographic regions; andtransforming the plurality of sets into a logically-equivalent totally-ordered set of non-overlapping geographic regions, wherein the transforming comprises:
iteratively inserting respective geographic regions of the plurality of sets, into the single set, in increasing order,wherein iteratively inserting the at least two overlapping geographic regions into the single set comprises performing one or more union operations on the at least two overlapping geographic regions to generate at least one orderable geographic region and inserting the at least one orderable geographic region into the single set in place of the at least two overlapping geographic regions; wherein dependent on the given logical operation's complexity, a requisite time to perform a search operation for a geographic location within the totally-ordered set of non-overlapping geographic regions is less than the requisite time to perform the given logical operation on the geographic regions.