Optimal combination of sampled measurements
Two regularized estimators that avoid the pathologies associated with variance estimation are disclosed. The regularized variance estimator adds a contribution to estimated variance representing the likely error, and hence ameliorates the pathologies of estimating small variances while at the same time allowing more reliable estimates to be balanced in the convex combination estimator. The bounded variance estimator employs an upper bound to the variance which avoids estimation pathologies when sampling probabilities are very small.
1. A method of estimating an attribute of objects, comprising:
a. obtaining a first sample of said objects based on a first sampling distribution;
b. obtaining a first estimate of said attribute based on said first sample;
c. obtaining a second sample of said objects based on a second sampling distribution, where said second sampling distribution is different from said first sampling distribution;
d. obtaining a second estimate of said attribute based on said second sample;
e. determining a lower bound for a variance based upon each of the first sample and the second sample; and
f. combining the first sample and the second sample using a variance value for each one of the first sample and the second sample that is equal to or larger than the lower bound for the variance for the first sample and second sample.
2. The method of claim 1 wherein the first and second samples are obtained at different locations.
3. The method of claim 1 wherein the first and second samples are obtained using different sampling algorithms.
4. The method of claim 1 wherein at least one of: said first sampling distribution or said second sampling distribution is obtained using a threshold sampling algorithm.
5. The method of claim 1 wherein at least one of: said first sampling distribution or said second sampling distribution is obtained using a priority sampling algorithm.
6. The method of claim 4 wherein at least one of: said first sampling distribution or said second sampling distribution is obtained using a parameter of the threshold sampling algorithm.
7. The method of claim 6 wherein said parameter is a value of a sampling threshold.
8. The method of claim 1 wherein the lower bound of the variance of each of the first sample and the second sample is obtained using information based on substantially all objects including those outside the first sample and the second sample, respectively.
9. The method of claim 1 wherein the lower bound of the variance of each of the first sample and the second sample is obtained using information based on individual objects that are part of the first sample and the second sample, respectively.
10. The method of claim 2 wherein the first and second samples are obtained at different router interfaces.
11. The method of claim 2 wherein the first and second samples are obtained at different routers.
12. The method of claim 2 wherein the first and second samples are obtained at different network ingress/egress interfaces.
13. The method of claim 1 wherein said objects are packets that traverse a network.
14. The method of claim 13 wherein the said attribute is the size of said packets.
15. A computer readable medium contained stored instructions which when executed on a computer causes the computer to perform a method of estimating an attribute of objects comprising:
a. obtaining a first sample of said objects based on a first sampling distribution;
b. obtaining a first estimate of said attribute based on said first sample;
c. obtaining a second sample of said objects based on a second sampling distribution, where said second sampling distribution is different from said first sampling distribution;
d. obtaining a second estimate of said attribute based on said second sample;
e. determining a lower bound for a variance based upon each of the first sample and the second sample; and
f. combining the first sample and the second sample using a variance value for each one of the first sample and the second sample that is equal to or larger than the lower bound for the variance for the first sample and second sample.
16. The computer readable medium of claim 15 wherein said objects are packets that traverse a network.
17. The computer readable medium of claim 16 wherein said attribute is the size of said packets.
18. The computer readable medium of claim 15 wherein the lower bound of the variance of each of the first sample and the second sample is obtained using information based on substantially all objects including those outside the first sample and the second sample, respectively.
19. The method computer readable medium of claim 15 wherein the lower bound of the variance of each of the first sample and the second sample is obtained using information based on individual objects that are part of the first sample and the second sample, respectively.