High-dimensional stratified sampling
View Patent ↗In one aspect, a processing device of an information processing system is operative to perform high-dimensional stratified sampling of a database comprising a plurality of records arranged in overlapping sub-groups. For a given record, the processing device determines which of the sub-groups the given record is associated with, and for each of the sub-groups associated with the given record, checks if a sampling rate of the sub-group is less than a specified sampling rate. If the sampling rate of each of the sub-groups is less than the specified sampling rate, the processing device samples the given record, and otherwise does not sample the given record. The determine, check and sample operations are repeated for additional records, and samples resulting from the sample operations are processed to generate information characterizing the database. Other aspects of the invention relate to determining which records to sample through iterative optimization of an objective function that may be based, for example, on a likelihood function of the sampled records.
1. An apparatus comprising:
a processing device comprising a processor having an associated memory;
wherein the processing device is operative:
to optimize an objective function characterizing which of a plurality of records in overlapping sub-groups of records are to be sampled, by iteratively updating components of a binary indicator that specifies whether or not respective ones of the plurality of records are sampled; and
to sample particular ones of the plurality of records based on values of the updated components of the binary indicator which optimize the objective function;
wherein samples resulting from the sample operation are processed to generate information characterizing a database comprising the sub-groups of records; and
wherein each of the components of the binary indicator characterizes a corresponding one of the plurality of records;
wherein at least one of the plurality of records is associated with two or more sub-groups.
2. The apparatus of claim 1 wherein the objective function is based on a binomial-normal approximation of a likelihood function of the sampled records.
3. The apparatus of claim 2 wherein the binary indicator is given by cε{0,1} N with Σ i=1 N c i =n such that c i indicates whether the ith record is sampled, where N denotes the number of records in the plurality of records, and n denotes the number of sampled records in the N records.
4. The apparatus of claim 3 wherein the objection function is based on an N×J sparse binary matrix A, where a particular entry A ij in the matrix A indicates whether or not the ith record is part of the jth sub-group, i=1, . . . , N, j=1, . . . , J, and said optimization utilizes sparse matrix operations performed on A.
5. The apparatus of claim 4 wherein the likelihood function of the sampled records is given by:
∏
j
=
1
J
(
n
j
s
j
)
p
s
j
(
1
-
p
)
n
j
-
s
j
and the corresponding binomial-normal approximation is given by:
∑
j
(
s
j
-
n
j
p
)
2
n
j
p
(
1
-
p
)
,
and wherein
n
j
=
∑
i
=
1
N
A
ij
s
j
=
∑
i
=
1
N
c
i
A
ij
denote number of records for the jth sub-group and number of sampled records for the jth sub-group, respectively, and p denotes sampling rate.
6. The apparatus of claim 5 wherein the objective function is given by
L
(
c
)
=
∑
j
(
A
j
T
c
-
n
j
p
)
2
n
j
p
(
1
-
p
)
and the objective function is optimized by minimizing L(c) with respect to c.
7. The apparatus of claim 1 wherein the processing device comprises a controller having a sampling module configured to perform said optimize and sample operations.
8. An integrated circuit comprising the apparatus of claim 1 .
9. A processor-implemented method comprising steps of:
optimizing an objective function characterizing which of a plurality of records in overlapping sub-groups of records are to be sampled, by iteratively updating components of a binary indicator that specifies whether or not respective ones of the plurality of records are sampled;
sampling particular ones of the plurality of records based on values of the updated components of the binary indicator which optimize the objective function; and
processing samples resulting from the sampling step to generate information characterizing a database comprising the plurality of records;
wherein each of the components of the binary indicator characterizes a corresponding one of the plurality of records;
wherein at least one of the plurality of records is associated with two or more sub-groups.
10. An article of manufacture comprising a non-transitory computer-readable storage medium having embodied therein executable program code that when executed by a processor of a processing device causes the device to perform the steps of the method of claim 9 .
11. The method of claim 9 wherein the objective function is based on a binomial-normal approximation of a likelihood function of the sampled records.
12. The method of claim 11 wherein the binary indicator is given by cε{0,1} N with Σ i=1 N c i =n such that c i indicates whether the ith record is sampled, where N denotes the number of records in the plurality of records, and n denotes the number of sampled records in the N records.
13. The method of claim 12 wherein the objection function is based on an N×J sparse binary matrix A, where a particular entry A ij in the matrix A indicates whether or not the ith record is part of the jth sub-group, i=1, . . . , N, j=1, . . . , J, and said optimization utilizes sparse matrix operations performed on A.
14. The method of claim 13 wherein the likelihood function of the sampled records is given by:
∏
j
=
1
J
(
n
j
s
j
)
p
s
j
(
1
-
p
)
n
j
-
s
j
and the corresponding binomial-normal approximation is given by:
∑
j
(
s
j
-
n
j
p
)
2
n
j
p
(
1
-
p
)
,
and wherein
n
j
=
∑
i
=
1
N
A
ij
s
j
=
∑
i
=
1
N
c
i
A
ij
denote number of records for the jth sub-group and number of sampled records for the jth sub-group, respectively, and p denotes sampling rate.
15. The method of claim 14 wherein the objective function is given by
L
(
c
)
=
∑
j
(
A
j
T
c
-
n
j
p
)
2
n
j
p
(
1
-
p
)
and the objective function is optimized by minimizing L(c) with respect to c.
16. The method of claim 9 wherein said optimizing and said sampling steps are performed in a sampling module of a processing device.