Methods, systems, and computer readable media for non-parametric dependence detection using bitwise operations in a computing system

1. A method for non-parametric dependence detection using bitwise operations in a computing system, the method comprising:

at a dependence detection module (DDM) in a computing system for analyzing big data, wherein the DDM is implemented using at least one processor, wherein the DDM detects non-parametric dependence in the big data:

receiving a set of p variables, wherein p represents an integer greater than or equal to two;

generating a set of binary interaction designs (BIDs) using a depth value d and bitwise operations, wherein each of the set of BIDs indicates a dependence structure based on arrangement of partitions in the respective BID;

determining, using the BIDs generated using bitwise operations in a computing system, non-parametric dependence between the set of p variables, wherein determining the non-parametric dependence between the set of p variables includes:

for each BID and for a number n of p-tuples, wherein each p-tuple contains a set of values for the set of p variables:

determining an amount of p-tuples located in a first partition type of two partition types in the respective BID; and

computing a probability value based on the amount of p-tuples located in the first partition type, wherein the non-parametric dependence between the set of p variables is determined when the probability value is equal to or exceeds a threshold value;

performing data analysis involving the set of p variables using the non-parametric dependence between the set of p variables; and

generating output related to the data analysis.

2. The method of claim 1 wherein performing the data analysis includes astronomy related analysis, genetic related analysis, pattern recognition, image recognition, speech recognition, medical related screening, or randomness testing.

3. The method of claim 1 wherein the covariate space of each BID is divided evenly between the two partition types, wherein each partition is of a width

1

2

d

.

4. The method of claim 1 wherein generating the set of BIDs using the depth value d and the bitwise operations includes constructing 2 d −1 configurations for a dimension, where the 2 d −1 configurations are generated from a d number of basic configurations.

5. The method of claim 4 wherein one of the basic configurations is computed using NOT (A i XOR (A i <<(1<<(d−i)))), wherein A i is a preceding basic configuration, XOR is a logical exclusive or operation, << is a bitwise left-shift operation, and NOT is a logical negation operation.

6. The method of claim 4 wherein a non-basic configuration of the 2 d −1 configurations is the dot product of at least two of the basic configurations.

7. The method of claim 1 wherein generating the set of BIDs using the depth value d and the bitwise operations includes calculating an empirical cumulative distribution function (CDF) for each variable.

8. The method of claim 1 wherein determining, using the BIDs generated using bitwise operations in a computing system, non-parametric dependence between the set of p variables includes generating a multiplicity adjusted probability value using a Bonferroni correction and the probability values associated with the BIDs, wherein the multiplicity adjusted probability value indicates the non-parametric dependence between the set of p variables.

9. The method of claim 1 wherein the threshold value is based on a probability value associated with a binomial distribution of the p-tuples among the first partition type of a BID.

10. A system for non-parametric dependence detection using bitwise operations in a computing system, the system comprising:

a computing system comprising:

at least one processor; and

a dependence detection module (DDM) implemented using the at least one processor, wherein the DDM detects non-parametric dependence in the big data, wherein the DDM is configured for:

receiving a set of p variables, wherein p represents an integer greater than or equal to two;

generating a set of binary interaction designs (BIDs) using a depth value d and bitwise operations, wherein each of the set of BIDs indicates a dependence structure based on arrangement of partitions in the respective BID;

determining, using the BIDs generated using bitwise operations in a computing system, non-parametric dependence between the set of p variables, wherein determining the non-parametric dependence between the set of p variables includes:

for each BID and for a number n of p-tuples, wherein each p-tuple contains a set of values for the set of p variables:

determining an amount of p-tuples located in a first partition type of two partition types in the respective BID; and

computing a probability value based on the amount of p-tuples located in the first partition type, wherein the non-parametric dependence between the set of p variables is determined when the probability value is equal to or exceeds a threshold value;

performing data analysis involving the set of p variables using the non-parametric dependence between the set of p variables; and

generating output related to the data analysis.

11. The system of claim 10 wherein performing the data analysis includes astronomy related analysis, genetic related analysis, pattern recognition, image recognition, speech recognition, medical related screening, or randomness testing.

12. The system of claim 10 wherein the covariate space of each BID is divided evenly between the two partition types and wherein each partition is of a width

1

2

d

.

13. The system of claim 10 wherein generating the set of BIDs using the depth value d and the bitwise operations includes constructing 2 d −1 configurations for a dimension, where the 2 d −1 configurations are generated from a d number of basic configurations.

14. The system of claim 13 wherein one of the basic configurations is computed using NOT (A i XOR (A i <<(1<<(d−i)))), wherein A i is a preceding basic configuration, XOR is a logical exclusive or operation, << is a bitwise left-shift operation, and NOT is a logical negation operation.

15. The system of claim 13 wherein a non-basic configuration of the 2 d −1 configurations is the dot product of at least two of the basic configurations.

16. The system of claim 10 wherein generating the set of BIDs using the depth value d and the bitwise operations includes calculating an empirical cumulative distribution function (CDF) for each variable.

17. The system of claim 10 wherein determining, using the BIDs generated using bitwise operations in a computing system, non-parametric dependence between the set of p variables includes generating a multiplicity adjusted probability value using a Bonferroni correction and the probability values associated with the BIDs, wherein the multiplicity adjusted probability value indicates the non-parametric dependence between the set of p variables.

18. The system of claim 10 wherein the threshold value is based on a probability value associated with a binomial distribution of the p-tuples among the first partition type of a BID.

19. A non-transitory computer readable medium having stored thereon executable instructions that when executed by at least one processor of a computer cause the computer to perform steps comprising:

at a dependence detection module (DDM) in a computing system for analyzing big data, wherein the DDM is implemented using at least one processor, wherein the DDM detects non-parametric dependence in the big data:

receiving a set of p variables, wherein p represents an integer greater than or equal to two;

generating a set of binary interaction designs (BIDs) using a depth value d and bitwise operations, wherein each of the set of BIDs indicates a dependence structure based on arrangement of partitions in the respective BID;

determining, using the BIDs generated using bitwise operations in a computing system, non-parametric dependence between the set of p variables, wherein determining the non-parametric dependence between the set of p variables includes:

for each BID and for a number n of p-tuples, wherein each p-tuple contains a set of values for the set of p variables:

determining an amount of p-tuples located in a first partition type of two partition types in the respective BID; and

computing a probability value based on the amount of p-tuples located in the first partition type, wherein the non-parametric dependence between the set of p variables is determined when the probability value is equal to or exceeds a threshold value;

performing data analysis involving the set of p variables using the non-parametric dependence between the set of p variables; and

generating output related to the data analysis.

20. The non-transitory computer readable medium of claim 19 wherein performing the data analysis includes astronomy related analysis, genetic related analysis, pattern recognition, image recognition, speech recognition, medical related screening, or randomness testing.