Systems, devices, and/or methods for determining dataset estimators

Abstract

Certain exemplary embodiments can provide a method, which can comprise automatically storing a sketch of a dataset that supports automatic determination of an estimator of properties of a dataset. The automatic determination can be based upon computed adjusted weights to the items included in a sketch of the dataset. The adjusted weights can be used to compute estimates on the weight of any subpopulation of the items in the dataset that is specified using a selection predicate. We propose the rank conditioning, the subset conditioning, and/or a Markov-chain based method to compute these adjusted weights. We also provide a method that provides upper and lower confidence bounds on the size of a subpopulation.

What is claimed is: 
     
       1. A method, comprising:
 obtaining an all-distance bottom-k sketch; 
 computing adjusted weights of the all-distance bottom-k sketch via a Markov-chain based method by utilizing a processor; 
 deriving a bottom-k sketch from the all-distance bottom-k sketch by utilizing the processor; 
 applying the adjusted weights to items in the bottom-k sketch by utilizing the processor; 
 estimating properties of flows through a router based upon the adjusted weights of the all-distance bottom-k sketch of the flows and based on corresponding estimators of a k-min sketch associated with the all-distance bottom-k sketch; 
 estimating a size of subpopulations of items of the flows based on the adjusted weights; and 
 calculating a selectivity of the subpopulations based on the adjusted weights. 
 
     
     
       2. A method, comprising:
 obtaining a sketch of a dataset having a format of at least one of a bottom-k sketch and an all-distance bottom-k sketch; 
 computing adjusted weights of the sketch of the dataset via a rank conditioning method by utilizing a processor; 
 deriving the bottom-k sketch from the all-distance bottom-k sketch by utilizing the processor; 
 applying the adjusted weights to items in the sketch of the dataset by utilizing the processor; 
 determining an estimator of properties of the dataset based on the sketch of the dataset, the adjusted weights, and on corresponding estimators of a k-min sketch associated with the all-distance bottom-k sketch; 
 rendering the estimator of the properties of the dataset; and 
 estimating a size of subpopulations of items of the dataset based on the adjusted weights. 
 
     
     
       3. The method of  claim 2 , further comprising
 summing the adjusted weights over the items of the subpopulations. 
 
     
     
       4. The method of  claim 2 , further comprising
 updating the bottom-k sketch in response to the items in the sketch of the dataset. 
 
     
     
       5. The method of  claim 2 , further comprising
 computing the adjusted weights via the rank conditioning method, wherein the rank conditioning method is configured to determine a rank conditioning estimator that has zero covariances between different records of the dataset. 
 
     
     
       6. The method of  claim 2 , further comprising
 computing the adjusted weights via a subset-conditioning method, wherein the estimator is based upon the adjusted weights. 
 
     
     
       7. The method of  claim 2 , further comprising
 computing the adjusted weights via a subset-conditioning method, wherein the subset-conditioning method is configured to compute a subset conditioning estimator, wherein the subset conditioning estimator has negative covariances between different records of the dataset. 
 
     
     
       8. The method of  claim 2 , further comprising
 computing the adjusted weights for items comprised in the all-distance bottom-k sketch, wherein the bottom-k sketch has exponentially distributed ranks and a known total weight. 
 
     
     
       9. The method of  claim 2 , further comprising
 calculating confidence intervals on subpopulation-size based upon the all-distance bottom-k sketch, wherein the estimator is based upon the confidence intervals. 
 
     
     
       10. The method of  claim 2 , further comprising
 estimating a variance of aid the estimator. 
 
     
     
       11. The method of  claim 2 , further comprising
 calculating a selectivity of the dataset based upon the adjusted weights. 
 
     
     
       12. The method of  claim 2 , further comprising
 answering a subpopulation weight query of the dataset based upon the adjusted weights. 
 
     
     
       13. The method of  claim 2 , further comprising
 determining a total weight of the dataset using the bottom-k sketch. 
 
     
     
       14. The method of  claim 2 , wherein
 the bottom-k sketch is a coordinated sketch of a plurality of bottom-k sketches. 
 
     
     
       15. The method of  claim 2 , wherein
 the bottom-k sketch comprises a single stored rank value. 
 
     
     
       16. The method of  claim 2 , wherein
 an underlying family of probability distributions used to determine rank values, upon which the bottom-k sketch is computed, are exponentially distributed with parameter equal to a weight of a corresponding item. 
 
     
     
       17. The method of  claim 2 , wherein
 the adjusted weights are unbiased. 
 
     
     
       18. A method, comprising:
 obtaining a sketch of a dataset having a format of at least one of a bottom-k sketch and an all-distance bottom-k sketch; 
 computing adjusted weights of the sketch of the dataset via a subset conditioning method by utilizing a processor; 
 deriving the bottom-k sketch from the all-distance bottom-k sketch by utilizing the processor; 
 applying the adjusted weights to items in the sketch of the dataset by utilizing the processor; 
 determining an estimator of properties of the dataset based on the sketch of the dataset, the adjusted weights, and on corresponding estimators of a k-min sketch associated with the all-distance bottom-k sketch; 
 rendering the estimator of the properties of the dataset; and 
 estimating a size of subpopulations of the items in the sketch of the dataset based on the adjusted weights. 
 
     
     
       19. A method, comprising:
 obtaining a sketch of a dataset having a format of at least one of a bottom-k sketch and an all-distance bottom-k sketch; 
 computing adjusted weights of the sketch via a Markov-chain based method by utilizing a processor; 
 deriving the bottom-k sketch from the all-distance bottom-k sketch by utilizing the processor; 
 applying the adjusted weights to items in the sketch of the dataset by utilizing the processor; 
 determining an estimator of properties of the dataset based on the sketch of the dataset, the adjusted weights, and on corresponding estimators of a k-min sketch associated with the all-distance bottom-k sketch; 
 rendering the estimator of the properties of the dataset; and 
 estimating a size of subpopulations of the items in the sketch of the dataset based on the adjusted weights. 
 
     
     
       20. The method of  claim 19 , further comprising determining a selectivity of the subpopulations based on the adjusted weights.