Multi-level data structure comparison using commutative digesting for unordered data collections
Techniques are provided for comparing multi-level data structures using commutative digesting for unordered data collections. One method comprises obtaining two multi-level data structures, wherein at least one multi-level data structure comprises an unordered data collection; determining a data structure digest value for each the two multi-level data structures by accumulating a data element digest value for each data element of the respective multi-level data structure, wherein a data element digest value for a given data element comprising an unordered data collection is determined using a commutative accumulator function; and evaluating a similarity of the two multi-level data structures by comparing the respective data structure digest values. A data element digest value for a given data element comprising an ordered data collection can be determined using a noncommutative accumulator function that aggregates a digest value for each data element using a noncommutative operation.
1. A method, comprising:
obtaining at least two different multi-level data structures each comprising a plurality of data elements, wherein at least one of the multi-level data structures comprises an unordered data collection, wherein an ordering of the data elements within a data collection does not have a meaning;
determining a data structure digest value for each of the at least two multi-level data structures by accumulating a data element digest value for each data element of the respective multi-level data structure, wherein a data element digest value, for a given data element comprising an unordered data collection, is determined using a commutative accumulator function, wherein the commutative accumulator function aggregates a digest value for each data element of the unordered data collection using one or more commutative operations;
evaluating a similarity of the at least two multi-level data structures by comparing the respective data structure digest values; and
automatically processing one or more of the at least two multi-level data structures using the evaluated similarity;
wherein the method is performed by at least one processing device comprising a processor coupled to a memory.
2. The method of claim 1 , wherein the commutative accumulator function generates a same digest value for the unordered data collection regardless of an iteration order over the unordered data collection.
3. The method of claim 1 , wherein determining the data structure digest value for a given multi-level data structure comprises recursively accumulating a data element digest value for each data element of the given multi-level data structure up to a root of the given multi-level data structure.
4. The method of claim 1 , wherein a data element digest value for a given data element comprising an ordered data collection is determined using a noncommutative accumulator function.
5. The method of claim 4 , wherein the noncommutative accumulator function aggregates a digest value for each data element of the ordered data collection using one or more noncommutative operations.
6. The method of claim 1 , wherein two of the multi-level data structures are considered equal data structures when the respective data structure digest values of the two the multi-level data structures match one another.
7. The method of claim 1 , further comprising evaluating configuration information of a given multi-level data structure to determine whether a given collection for the given multi-level data structure comprises an unordered data collection or an ordered data collection.
8. The method of claim 1 , wherein the automatic processing of the one or more of the at least two multi-level data structures using the evaluated similarity of the at least two multi-level data structures comprises one or more of: (i) comparing computed data associated with a first one of the at least two multi-level data structures with expected data associated with a second one of the at least two multi-level data structures using the evaluated similarity, (ii) determining whether data of at least one of the at least two multi-level data structures has changed based at least in part on the evaluated similarity and (iii) triggering a process or application only when a data change is detected, using the evaluated similarity, in a multi-level data structure processed by the process or application.
9. The method of claim 1 , wherein a digest function that determines one or more of the digest values is characterized by one or more of the following properties: the digest value for a given data element is always the same value, the digest value for the given data element is computed quickly, the digest value for the given data element changes significantly for any change to the given data element, and the digest value for the given data element has a low collision probability with respect to the digest values for other data elements.
10. An apparatus comprising:
at least one processing device comprising a processor coupled to a memory;
the at least one processing device being configured to implement the following steps:
obtaining at least two different multi-level data structures each comprising a plurality of data elements, wherein at least one of the multi-level data structures comprises an unordered data collection, wherein an ordering of the data elements within a data collection does not have a meaning;
determining a data structure digest value for each of the at least two multi-level data structures by accumulating a data element digest value for each data element of the respective multi-level data structure, wherein a data element digest value, for a given data element comprising an unordered data collection, is determined using a commutative accumulator function, wherein the commutative accumulator function aggregates a digest value for each data element of the unordered data collection using one or more commutative operations;
evaluating a similarity of the at least two multi-level data structures by comparing the respective data structure digest values; and
automatically processing one or more of the at least two multi-level data structures using the evaluated similarity.
11. The apparatus of claim 10 , wherein a data element digest value for a given data element comprising an ordered data collection is determined using a noncommutative accumulator function that aggregates a digest value for each data element of the ordered data collection using one or more noncommutative operations.
12. The apparatus of claim 10 , further comprising evaluating configuration information of a given multi-level data structure to determine whether a given collection for the given multi-level data structure comprises an unordered data collection or an ordered data collection.
13. The apparatus of claim 10 , wherein the automatic processing of the one or more of the at least two multi-level data structures using the evaluated similarity of the at least two multi-level data structures comprises one or more of: (i) comparing computed data associated with a first one of the at least two multi-level data structures with expected data associated with a second one of the at least two multi-level data structures using the evaluated similarity, (ii) determining whether data of at least one of the at least two multi-level data structures has changed based at least in part on the evaluated similarity and (iii) triggering a process or application only when a data change is detected, using the evaluated similarity, in a multi-level data structure processed by the process or application.
14. The apparatus of claim 10 , wherein the commutative accumulator function generates a same digest value for the unordered data collection regardless of an iteration order over the unordered data collection.
15. A non-transitory processor-readable storage medium having stored therein program code of one or more software programs, wherein the program code when executed by at least one processing device causes the at least one processing device to perform the following steps:
obtaining at least two different multi-level data structures each comprising a plurality of data elements, wherein at least one of the multi-level data structures comprises an unordered data collection, wherein an ordering of the data elements within a data collection does not have a meaning;
determining a data structure digest value for each of the at least two multi-level data structures by accumulating a data element digest value for each data element of the respective multi-level data structure, wherein a data element digest value, for a given data element comprising an unordered data collection, is determined using a commutative accumulator function, wherein the commutative accumulator function aggregates a digest value for each data element of the unordered data collection using one or more commutative operations;
evaluating a similarity of the at least two multi-level data structures by comparing the respective data structure digest values; and
automatically processing one or more of the at least two multi-level data structures using the evaluated similarity.
16. The non-transitory processor-readable storage medium of claim 15 , wherein a data element digest value for a given data element comprising an ordered data collection is determined using a noncommutative accumulator function that aggregates a digest value for each data element of the ordered data collection using one or more noncommutative operations.
17. The non-transitory processor-readable storage medium of claim 15 , further comprising evaluating configuration information of a given multi-level data structure to determine whether a given collection for the given multi-level data structure comprises an unordered data collection or an ordered data collection.
18. The non-transitory processor-readable storage medium of claim 15 , wherein the automatic processing of the one or more of the at least two multi-level data structures using the evaluated similarity of the at least two multi-level data structures comprises one or more of: (i) comparing computed data associated with a first one of the at least two multi-level data structures with expected data associated with a second one of the at least two multi-level data structures using the evaluated similarity, (ii) determining whether data of at least one of the at least two multi-level data structures has changed based at least in part on the evaluated similarity and (iii) triggering a process or application only when a data change is detected, using the evaluated similarity, in a multi-level data structure processed by the process or application.
19. The non-transitory processor-readable storage medium of claim 15 , wherein the commutative accumulator function generates a same digest value for the unordered data collection regardless of an iteration order over the unordered data collection.
20. The non-transitory processor-readable storage medium of claim 15 , wherein determining the data structure digest value for a given multi-level data structure comprises recursively accumulating a data element digest value for each data element of the given multi-level data structure up to a root of the given multi-level data structure.