Systems and methods for extracting signal differences from sparse data sets

• US 10,445,312 B1
• Filed: 10/14/2016
• Issued: 10/15/2019
• Est. Priority Date: 10/14/2016
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Lewis, Justin, James, Gavin
• Primary Examiner(s): Robinson, Greta L
• Application Number:
  US15/294,267
• Time in Patent Office: 1,096 Days
• Field of Search: 707607, 707802, 707807, 707809, 707810, 707811
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity

Abstract

The present disclosure provides systems and methods for extracting signal differences from sparse data sets. Data sets for comparison, including a control data set and one or more test data sets, may be normalized and separated into subsets or groupings via a MapReduce function. Normalization may account for large values present in both control and test data sets that would otherwise reduce the significance of smaller correlated values, creating false negatives. The MapReduce may provide identification and analysis of correlations between sets via related entities. Accordingly, via the systems and methods discussed herein, a computing device may extract statistically significant differences between data sets, without requiring extensive entity by entity comparison (or entity to every entity comparison, which, for a data set of millions of entities, may be too computationally expensive or take too long), reducing memory footprint and processor requirements.

Claims

1. A method for calculating signal differences from a sparse data set signal, comprising:

generating, by a signal aggregator executed by a measurement engine of a computing device, a first data set comprising a first number of null values and a second number of non-null values, the first number at least an order of magnitude larger than the second number;

normalizing, by a signal correlator executed by the measurement engine, each non-null value of the second number of non-null values relative to a total of the non-null values of the first data set;

separating, by the signal correlator, the first data set into a plurality of subsets comprising one or more null values and one or more non-null values; and

for at least one subset of the plurality of subsets;

calculating a difference value, by the signal correlator, between the at least one subset and a corresponding subset of a second plurality of subsets generated from a second data set, the difference value indicating a level that first characteristics of the at least one subset differs from second characteristics of the corresponding subset; and

writing an identification of the subset as including a signal to a memory device, responsive to the difference value exceeding a threshold.

2. The method of claim 1, further comprising, for a second subset of the plurality of subsets:

calculating a second difference value, by the signal correlator, between the second subset and a second corresponding subset of the second plurality of subsets generated from the second data set; and

writing an identification of the second subset as not including a signal to the memory device, responsive to the difference value not exceeding the threshold.

3. The method of claim 1, wherein normalizing each non-null value comprises calculating a logarithm of the non-null value to a base of a sum of the non-null values of the first data set.

4. The method of claim 1, wherein the first data set and second data set comprise measured null and non-null values for a predetermined plurality of items.

5. The method of claim 4, wherein the predetermined plurality of items are grouped into the plurality of subsets;

wherein separating the first data set into the plurality of subsets comprises, for each subset, calculating a sum of the non-null values measured for items in the subset.

6. The method of claim 5, further comprising selecting an item of the predetermined plurality of items.

7. The method of claim 1, further comprising:

generating, by the signal aggregator, the second data set comprising a third number of null values and a fourth number of non-null values;

normalizing, by the signal correlator, each non-null value of the fourth number of non-null values relative to a total of the non-null values of the second data set; and

separating, by the signal correlator, the second data set into the plurality of subsets.

8. The method of claim 1, wherein the first data set and second data set comprise a plurality of identifications of a number of requests for each of a plurality of media items by a first population and non-overlapping second population, respectively.

9. A system for calculating signal differences from a sparse data set signal, comprising:

a processor executing a measurement engine comprising a signal aggregator and a signal correlator, and a memory device storing a first data set and a second data set;

wherein the signal aggregator is configured to generate the first data set comprising a first number of null values and a second number of non-null values, the first number at least an order of magnitude larger than the second number; and

wherein the signal correlator is configured to;

normalize each non-null value of the second number of non-null values relative to a total of the non-null values of the first data set,

separate the first data set into a plurality of subsets comprising one or more null values and one or more non-null values, and

for at least one subset of the plurality of subsets;

calculate a difference value between the at least one subset and a corresponding subset of a second plurality of subsets generated from a second data set, the difference value indicating a level that first characteristics of the at least one subset differs from second characteristics of the corresponding subset; and

write an identification of the subset as including a signal to the memory device, responsive to the difference value exceeding a threshold.

10. The system of claim 9, wherein the signal correlator is further configured to, for a second subset of the plurality of subsets:

calculate a second difference value between the second subset and a corresponding subset of the second plurality of subsets generated from the second data set; and

write an identification of the second subset as not including a signal to the memory device, responsive to the second difference value not exceeding the threshold.

11. The system of claim 9, wherein the signal correlator is further configured to calculate a logarithm of the non-null value to a base of a sum of the non-null values of the first data set.

12. The system of claim 9, wherein the first data set and second data set comprise measured null and non-null values for a predetermined plurality of items.

13. The system of claim 12, wherein the predetermined plurality of items are grouped into the plurality of subsets;

wherein the signal correlator is further configured to, for each subset, calculate a sum of the non-null values measured for items in the subset.

14. The system of claim 13, wherein the signal correlator is further configured to select an item of the predetermined plurality of items.

15. The system of claim 9, wherein the signal aggregator is further configured to generate the second data set comprising a third number of null values and a fourth number of non-null values;

and

wherein the signal correlator is further configured to;

normalize, by the signal analyzer, each non-null value of the fourth number of non-null values relative to a total of the non-null values of the second data set, and

separate the second data set into the plurality of subsets.

16. The system of claim 9, wherein the first data set and second data set comprise a plurality of identifications of a number of requests for each of a plurality of media items by a first population and non-overlapping second population, respectively.

17. A non-transitory computer-readable medium storing instructions that, when executed by a processor, cause the processor to:

generate a first data set comprising a first number of null values and a second number of non-null values, the first number at least an order of magnitude larger than the second number;

normalize each non-null value of the second number of non-null values relative to a total of the non-null values of the first data set;

separate the first data set into a plurality of subsets comprising one or more null values and one or more non-null values;

for at least one subset of the plurality of subsets;

calculate a difference value between the at least one subset and a corresponding subset of a second plurality of subsets generated from a second data set, the difference value indicating a level that first characteristics of the at least one subset differs from second characteristics of the corresponding subset; and

write an identification of the subset as including a signal to a memory device, responsive to the difference value exceeding a threshold; and

for at least one second subset of the plurality of subsets;

calculate a second difference value between the second subset and a second corresponding subset of the second plurality of subsets generated from the second data set, the second difference value indicating a second level that third characteristics of the at least one second subset differs from fourth characteristics of the second corresponding subset; and

write an identification of the second subset as not including a second signal to the memory device, responsive to the second difference value not exceeding the threshold.

18. The computer readable medium of claim 17, wherein execution of the instructions further cause the processor to calculate a logarithm of the non-null value to a base of a sum of the non-null values of the first data set.

19. The computer readable medium of claim 17, wherein the first data set and second data set comprise measured null and non-null values for a predetermined plurality of items, and wherein the predetermined plurality of items are grouped into the plurality of subsets;

wherein execution of the instructions further cause the processor to calculate a sum of the non-null values measured for items in the subset and select an item of the predetermined plurality of items.

20. The computer readable medium of claim 17, wherein execution of the instructions further cause the processor to generate the second data set comprising a third number of null values and a fourth number of non-null values;

normalize each non-null value of the fourth number of non-null values relative to a total of the non-null values of the second data set; and

separate the second data set into the plurality of subsets.