Methods and data structures for efficient cross-referencing of physical-asset spatial identifiers
Described herein are methods, systems, and storage media having computer-processable instructions for cross-referencing in a computationally efficient manner different data sets each having pluralities of n-dimensional identifiers of physical assets. The disclosed cross-referencing approach can be used to determine relationships between different assets and their respective asset identifier strings. The relationships can be established based on user-selected heuristics. For example, at least two asset identifier strings can be compared, and user-defined heuristics can be applied to determine whether “a match” exists. A match can be defined according to the particular heuristic. In one instance, the comparison and heuristic can be applied to determine if two different asset identifier strings refer to a single physical asset.
1. A method of cross-referencing different sets of asset identifiers, the method comprising the steps of:
providing first and second data sets comprising records, each record comprising an n-dimensional asset identifier that encodes a center-of-mass position and center-of-mass-to-bounding-polytope extents along n dimensions (n≥2) of a physical asset in a single, non-opaque, computer-readable code string;
constructing first and second trie data structures based on the first and second data sets, respectively, wherein each layer of the trie data structure corresponds with a successive degree of spatial resolution and each leaf node in a layer comprises a subset of n-dimensional asset identifiers co-located in an n-dimensional grid cell;
zipping the first and second trie data structures at a predetermined level of spatial resolution to yield a coproduct of the subsets from a pair of first and second trie-data-structure leaf nodes, the coproduct comprising a list of candidate cross-referenced pairs of records from the first and second data sets;
calculating a spatially-based statistic associated with a predetermined heuristic for the n-dimensional asset identifiers in a pair of nodes; and
applying the predetermined heuristic to select a cross-referenced pair of records from the list of candidate cross-referenced pairs wherein calculating the spatially-based statistic further comprises the steps of decoding an n-dimensional asset identifier to yield its center of mass and its center-of-mass-to-bounding-polytope extents, labeling respective asset identifiers in a candidate cross-referenced pair as having either the least or greatest area, and calculating the Euclidean distance between centers of mass for the candidate cross-referenced pair, wherein the predetermined heuristic comprises the pair of n-dimensional asset identifiers for which a percentage area of intersection for bounding boxes with the least area is greatest and for which a distance between two centers of mass is lowest.
2. The method of claim 1 , wherein said constructing first and second trie data structures further comprises the step of constructing first and second trie data structures based on a portion of the first and second data sets determined by the predetermined spatial resolution.
3. The method of claim 1 , wherein the spatially-based statistic comprises a record-level statistic, a node-level statistic, trie-data-structure level statistic, a data-set-level statistic, or a combination thereof.
4. The method of claim 1 , wherein the predetermined heuristic comprises a maximum percentage area of intersection for bounding boxes for a pair of asset identifiers.
5. The method of claim 1 , wherein the predetermined heuristic comprises a minimum distance between centers of mass for a pair of asset identifiers.
6. The method of claim 1 , wherein the predetermined heuristic comprises one n-dimensional asset identifier contains another.
7. The method of claim 1 , further comprising indexing the first data set, the second data set, or both to enhance computational efficiency.
8. The method of claim 1 , wherein the first data set, the second data set, or both comprise a delimiter-separated values file or a spatial data format shapefile.
9. The method of claim 1 , wherein at least one record further comprises an attribute associated with an asset identifier of the at least one record.
10. The method of claim 9 , wherein the attribute comprises asset characteristics, asset description, asset make, asset model, asset ownership, or a combination thereof.
11. The method of claim 1 , wherein n≥3.
12. The method of claim 1 , further comprising the step of filtering the records of the first data set, the records of the second data set or both at a record-level, a node-level, a trie-data-structure level, a data-set level, or a combination thereof.
13. The method of claim 1 , further comprising the step of filtering members of the list of candidate cross-referenced pairs.
14. A non-transitory computer readable storage medium storing one or more programs, the one or more programs comprising instructions, which are executed by one or more processors to:
provide first and second data sets comprising records, each record comprising an n-dimensional asset identifier that encodes a center-of-mass position and center-of-mass-to-bounding-polytope extents along n dimensions (n≥2) of a physical asset in a single, non-opaque, computer-readable code string;
construct first and second trie data structures based on the first and second data sets, respectively, wherein each layer of the trie data structure corresponds with a successive degree of spatial resolution and each leaf node in a layer comprises a subset of n-dimensional asset identifiers co-located in an n-dimensional grid cell;
zip the first and second trie data structures at a predetermined level of spatial resolution to yield a coproduct of the subsets from a pair of first and second trie-data-structure leaf nodes, the coproduct comprising a list of candidate cross-referenced pairs of records from the first and second data sets;
calculate a spatially-based statistic associated with a predetermined heuristic for the n-dimensional asset identifiers in a pair of nodes; and
apply the predetermined heuristic to select a cross-referenced pair of records from the list of candidate cross-referenced pairs, wherein the instructions, which are executed to calculate the spatially-based statistic, further comprise instructions, which are executed to:
decode an n-dimensional asset identifier to yield its center of mass and its center-of-mass-to-bounding-polytope extents;
label respective asset identifiers in a candidate cross-referenced pair as having either the least or greatest area; and
calculate the Euclidean distance between centers of mass for the candidate cross-referenced pair;
wherein the predetermined heuristic comprises the pair of n-dimensional asset identifiers for which a percentage area of intersection for bounding boxes with the least area is greatest and for which a distance between two centers of mass is lowest.
15. The non-transitory computer-readable storage medium of claim 14 , wherein the instructions, which are executed to construct first and second trie data structures, further comprise instructions, which are executed to construct first and second trie data structures based on a portion of the first and second data sets determined by the predetermined spatial resolution.
16. The non-transitory computer readable storage medium of claim 14 , storing programs comprising instructions, which are executed to further:
filter the records of the first data set, the records of the second data set or both at a record-level, a node-level, a trie-data-structure level, a data-set level, or a combination thereof.