Determination of sampling characteristics based on available memory

• US 7,818,534 B2
• Filed: 05/09/2007
• Issued: 10/19/2010
• Est. Priority Date: 05/09/2007
• Status: Expired due to Fees

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Selle, Brian T., Shanbhag, Amit Umesh, Burgess, David A., Ames, Glen Anthony, Rajagopalan, Sundara Raman
• Primary Examiner(s): Bragdon; Reginald G
• Assistant Examiner(s): Sadler; Nathan
• Application Number:
  US11/746,541
• Publication Number:
  US 20080282020A1
• Time in Patent Office: 1,259 Days
• Field of Search: 711/171, 711/172, 707/270
• US Class Current: 711/172
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

A portion of data records of a full input data set are imported into memory of a computer system for processing by an executing application. The full input data set includes data records of a dimensionally-modeled fact collection. An amount of the data of the full input set to import is determined based on an amount of available memory of the computer system. The sampling characteristics for sampling the full input data set are determined based on the amount of the data that can be imported and on characteristics of the full input data set and application involved. The full input data set is then sampled and a portion of the records are imported into the memory of the computer system for processing. The sampling characteristics are determined such that analysis as a result of processing by the executing application of the sampled portion of the records imported is representative of the analysis that could otherwise be carried out on the full input data set, with a calculable statistical relevance.

Claims

1. A computer-implemented method comprising:

importing a portion of a full input data set into memory accessible by one or more computing devices for processing by an executing application, wherein the full input data set comprises a plurality of data records representing a dimensionally-modeled fact collection and wherein each record comprises a plurality of characteristics of an entity, the importing of the portion of the full input data set comprising;

determining an amount of the data of the full input data set to import based on an amount of available memory accessible to the one or more computing devices;

based on the determined amount of the data to import and on characteristics of the full input data set other than the total size of the full input data set, determining sampling characteristics for sampling the full input data set to sample less than every record of the full input set,

wherein the determined sampling characteristics are determined in part based on an indication of how many of the records have one or more particular values for one or more particular entity characteristics such that if a determined statistical significance achievable using the determined sampling characteristics does not meet a user-provided desired statistical significance for records with the particular values for the particular entity characteristics, the determined sampling characteristics are adjusted to meet the user-provided desired statistical significance for such records; and

causing the portion of the full input data set to be imported into the memory of the computer system, including sampling the full input data set, to determine the portion of the records to import, in accordance with the determined sampling characteristics,

wherein the adjusted sampling characteristics are such that analysis as a result of processing by the executing application of the sampled portion of the full input data set is representative of the analysis that could otherwise be carried out on the full input data set, with a calculable statistical relevance,

wherein sampling the full input data set using the adjusted sampling characteristics is performed in a deterministic manner such that records of the full input data set having the particular values for the particular entity characteristics are included in the sampled portion of the full input data set in an amount sufficient to meet the user-provided desired statistical significance for such records, and

wherein sampling the full input data set to determine the portion of the records to import includes applying a hash algorithm for sampling based on a key that is the value for each record at a particular dimension, the dimension in question being one that identifies a particular entity or user, wherein remaining information in each data record includes information regarding behavior or traits of the particular entity or user identified by the key for that record.

2. The computer-implemented method of claim 1, wherein:

sampling the full input data set, to determine the portion of the records to import, includes sampling such that, for each record of the full input data set sampled, wherein that input record has information about a particular entity, every record of the full input data set including information regarding behavior of the particular entity is sampled.

3. The computer-implemented method of claim 1, further comprising:

analyzing the sampled data records, including determining a statistical confidence for the analysis; and

causing a result of the analysis, including the determined statistical confidence, to be made available to a user.

4. The computer-implemented method of claim 1, wherein:

determining an amount of the data of the full input set to import based on an amount of available memory of the computer system includes determining the amount of the data in memory to be less than the amount of available memory of the computer system.

5. The computer-implemented method of claim 1, wherein:

sampling the full input data set, to determine the portion of the records to import, includes

assigning the full input data set into a plurality of bins, wherein for each record of the full input data set sampled, that input record has a particular value at a particular dimension and every record of the full input data set having the particular value at the particular dimension is in that same bin; and

sampling all the records of at least one of the bins.

6. A computer-implemented method comprising:

importing a portion of a full input data set into memory accessible by one or more computing devices for processing by an executing application, wherein the full input data set comprises a plurality of data records representing a dimensionally-modeled fact collection and wherein each record comprises a plurality of characteristics of an entity, the importing of the portion of the full input data set comprising;

determining a nominal amount of the data of the full input set to import based on an amount of available memory accessible to the one or more computing devices;

based on the determined amount of the data to import and on characteristics of the full input data set other than the total size of the full input data set, determining sampling characteristics for sampling the full input data set;

determining a characteristic associated with the determined amount of data, the characteristic relating to how many of the records have one or more particular values for one or more particular entity characteristics;

causing the computing device to adjust the determined sampling characteristics when a user-provided desired statistical significance for records having the particular values for the particular entity characteristics is not met by the determined characteristic associated with the determined amount of data; and

causing the portion of the full input data set to be imported into the memory of the computer system, including sampling the full input data set, to determine the portion of the records to import, in accordance with the adjusted sampling characteristics,

wherein sampling the full input data set using the adjusted sampling characteristics is performed in a deterministic manner such that records of the full input data set having the particular values for the particular entity characteristics are included in the sampled portion of the full input data set in an amount sufficient to meet the user-provided desired statistical significance for such records, and

wherein sampling the full input data set to determine the portion of the records to import includes applying a hash algorithm for sampling based on a key that is the value for each record at a particular dimension, the dimension in question being one that identifies a particular entity or user, wherein remaining information in each data record includes information regarding behavior or traits of the particular entity or user identified by the key for that record.

7. The computer-implemented method of claim 6, wherein:

the adjusted sampling characteristics include characteristics corresponding to inputting the portion of records a sub-portion at a time, wherein analysis is carried out on the imported sub-portions while the others of the sub-portions are not present in the memory.

8. The computer-implemented method of claim 6, wherein:

the adjusted sampling characteristics include characteristics corresponding to inputting less than the determined nominal amount of the full input data set.

9. The computer-implemented method of claim 6, wherein:

the determined characteristic associated with the determined amount of data includes at least one of the group consisting of

statistical confidence for analysis that would be achievable if carried out based on the determined amount of data;

an amount of time to import the determined amount of data; and

a percentage of the full input data set of which the determined amount of data comprises.

10. A computing device comprising processing circuitry and memory circuitry, wherein the computing device is configured to import an amount of data of a full input data set that is a portion of the full input data set, wherein the full input data set comprises a plurality of data records representing a dimensionally-modeled fact collection and each record comprises a plurality of characteristics of an entity, wherein the portion of the full input data set to import has been determined by:

determining an amount of the data of the full input set to import based on an amount of available memory accessible to the one or more computing devices;

based on the determined amount of the data to import and on characteristics of the full input data set other than the total size of the full input data set, determining sampling characteristics for sampling the full input data set,

wherein the determined sampling characteristics are determined in part based on an indication of how many of the records have one or more particular values for one or more particular entity characteristics such that if a determined statistical significance achievable using the determined sampling characteristics does not meet a user-provided desired statistical significance for records with the particular values for the particular entity characteristics, the determined sampling characteristics are adjusted to meet the user-provided desired statistical significance for such records; and

sampling the full input data set, to determine the portion of the records to import, in accordance with the determined sampling characteristics,

wherein the adjusted sampling characteristics are such that analysis as a result of processing by the executing application of the sampled portion of the full input data set is representative of the analysis that could otherwise be carried out on the full input data set, with a calculable statistical relevance,

wherein sampling the full input data set using the adjusted sampling characteristics is performed in a deterministic manner such that records of the full input data set having the particular values for the particular entity characteristics are included in the sampled portion of the full input data set in an amount sufficient to meet the user-provided desired statistical significance for such records, and

wherein sampling the full input data set to determine the portion of the records to import includes applying a hash algorithm for sampling based on a key that is the value for each record at a particular dimension, the dimension in question being one that identifies a particular entity or user, wherein remaining information in each data record includes information regarding behavior or traits of the particular entity or user identified by the key for that record.

11. The computing device of claim 10, wherein:

the computing device is further configured to process the portion of the full input data set.

12. The computing device of claim 10, wherein:

the computing device is further configured to cause a representation of the portion of the full input data set to be displayed.

13. A computer program product comprising at least one computer-readable storage medium having computer program instructions stored therein which are operable to cause at least one computing device to:

import a portion of a full input data set into memory accessible by one or more computing devices for processing by an executing application, wherein the full input data set comprises a plurality of data records representing a dimensionally-modeled fact collection and wherein each record comprises a plurality of characteristics of an entity, the importing of the portion of the full input data set comprising;

determine an amount of the data of the full input set to import based on an amount of available memory accessible to the one or more computing devices;

based on the determined amount of the data to import and on characteristics of the full input data set other than the total size of the full input data set, determine sampling characteristics for sampling the full input data set,

wherein the determined sampling characteristics are determined in part based on an indication of how many of the records have one or more particular values for one or more particular entity characteristics such that if a determined statistical significance achievable using the determined sampling characteristics does not meet a user-provided desired statistical significance for records with the particular values for the particular entity characteristics, the determined sampling characteristics are adjusted to meet the user-provided desired statistical significance for such records; and

cause the portion of the full input data set to be imported into the memory of the computer system, including sampling the full input data set, to determine the portion of the full input data set to import, in accordance with the determined sampling characteristics, wherein the adjusted sampling characteristics are such that analysis as a result of processing by the executing application of the sampled portion of the full input data set is representative of the analysis that could otherwise be carried out on the full input data set, with a calculable statistical relevance,

wherein the computer program instructions operable to cause the at least one computing device to sample the full input data set to determine the portion of the full input data set to import includes computer program instructions operable to cause the at least one computing device to sample the full input data set in a deterministic manner such that records of the full input data set having the particular values for the particular entity characteristics are included in the sampled portion of the full input data set in an amount sufficient to meet the user-provided desired statistical significance for such records, and

wherein sampling the full input data set to determine the portion of the records to import includes applying a hash algorithm for sampling based on a key that is the value for each record at a particular dimension, the dimension in question being one that identifies a particular entity or user, wherein remaining information in each data record includes information regarding behavior or traits of the particular entity or user identified by the key for that record.

14. The computer program product of claim 13, wherein:

the computer program instructions operable to cause the at least one computing device to sample the full input data set, to determine the portion of the records to import includes computer program instructions operable to sample such that, for each record of the full input data set sampled, wherein that input record has information about a particular user, every record of the full input data set including information regarding behavior of the particular user is sampled.

15. The computer program product of claim 14, wherein the computer program instructions further include computer program instructions operable to cause the at least one computing device to:

analyze the sampled data records, including determining a statistical confidence for the analysis; and

cause a result of the analysis, including the determined statistical confidence, to be made available to a user.

16. The computer program product of claim 13, wherein the computer program instructions operable to cause the at least one computing device to determine an amount of the data of the full input set to import based on an amount of available memory of the computer system includes computer program instructions operable to cause the at least one computing device to:

determine the amount of the data to be less than the amount of available memory of the computer system.

17. The computer program product of claim 13, wherein the computer program instructions operable to cause the at least one computing device to sample the full input data set, to determine the portion of the records to import includes computer program instructions operable to cause the at least one computing device to:

assign the full input data set into a plurality of bins, wherein for each record of the full input data set sampled, that input record has a particular value at a particular dimension and every record of the full input data set having the particular value at the particular dimension is in that same bin; and

sample all the records of at least one of the bins.