to denote the variance of ni.We rely on the following theorem C.Compute the Optimal Granularity for Ensemble Sampling to illustrate the accuracy of the estimator SE. Theorem I:Let o;represent the variance of the estimator SE As indicated in the above analysis,during a query cycle mi,the load factor p=子，then, of the ensemble sampling,in order to achieve the accuracy requirement for all categories,the essential scanning time d=%.eP+n-1 mainly depends on the category with the smallest tag size. n'co+n-1(6+n2)-n. (7) as the other categories must still be involved in the query cycle until this category achieves the accuracy requirement. Proof:See Appendix A. Therefore,we use the notion group to define a set of categories 2)Reducing the Variance through Repeated Tests:As the involved in a query cycle of the ensemble sampling.Hence, frame size for each query cycle has a maximum value,by each cycle of ensemble sampling should be applied over an estimating from the ensemble sampling within only one query appropriate group,such that the variance of the tag sizes for cycle,the estimated tag size may not be accurate enough for the involved categories cannot be too large.In this way,all the accuracy constraint.In this situation,multiple query cycles categories in the same group achieve the accuracy requirement are essential to reduce the variance through repeated tests. with very close finishing time.In addition,according to Eq.(7), Suppose the reader issues l query cycles over the same set of as the number of categories increases in the ensemble sampling categories,in regard to a specified category Ci,by utilizing the the load factor p is increased,then the achieved accuracy for weighted statistical averaging method,the averaged tag size each involved category is reduced.Therefore,it is essential to 元=∑k=1uknk:here wk=】 工，n,k and 6.k 1 compute an optimal granularity for the group in regard to the respectively denote the estimated tag size and variance for each reading performance.Suppose there exists m categories in total, cycle k.Then,the variance of元iso=zi本 the objective is to divide them into d(1 sd m)groups for ensemble sampling,such that the overall scanning time can be Therefore,according to the accuracy constraint in the prob- minimized while achieving the accuracy requirement. lem formulation,we rely on the following theorem to express For a specified group,in order for all involved categories to this constraint in the form of the variance. satisfy the accuracy requirement,it is essential to compute the Theorem 2:Suppose the variance of the averaged tag size required frame size for the category with the smallest tag size, nis o.The accuracy constraint is satisfied for a specified category C,as long as子≤(zaaP.n,Zi-aa is the say nLet(then,according to Theorem 2. we can compute the essential frame size f such that Ai(f)<ti. 1-percentile for the standard normal distribution. Assume that the inter-cycle overhead is Te,and the average Proof:See Appendix B. ■ time interval per slot is Ts.Therefore,if f fmaz,then the According to Theorem 2,we can verify if the accuracy con- total scanning time T f.Ts+Te.Otherwise,if the final straint is satisfied for each category through directly checking estimate is the average of r independent experiments each with the variance against the threshold If 1-5%. an estimator variance of Ai(fmaz),then the variance of the then Z1-B/2=1.96. average is).Hence,if we want the final variance to 3)Property of the Ensemble Sampling:According to The- bet thenr should be,the total scanning time is orem 1,the normalized variance of the SE estimator A;=5 n T=(fmax·Ts+Tc)·r. is equivalent to=(().Let n(eP+n-1)1 We propose a dynamic programming-based algorithm to ep+n-1 a 告.b=e号Then,the normalized compute the optimal granularity for ensemble sampling.As- ep-n-I variance i=a.+b.Since the SE estimator can utilize sume that currently there are m categories,ranked in non- any estimator like [4][12][15]to estimate the overall tag size, increasing order,according to the estimated tag size,e.g., then,without loss of generality,if we use the estimator in [4], C1,C2,....Cm.We need to cut the ranked categories into one or more continuous groups for ensemble sampling.In regard to a we can prove that a <0 for any value of n>0,f >0.This property applies to any estimator with variance smaller than 8o single group consisting of categories from Ci to Ci,we define t(i,j)as the essential scanning time for ensemble sampling, in ZE,which simply estimates the overall tag size based on the which is computed in the same way as aforementioned T.Fur- observed number of empty slots. According to Theorem 2,in order to satisfy the accuracy thermore,we define T(i,j)as the minimum overall scanning constraint,we should ensure that( )2.ni.As a<0 time over the categories from Ci to Ci among various grouping strategies.Then,the recursive expression of T(i,j)is shown for all values of f,it infers that the larger the value ni is, in Eq.(8) the faster it will be for the specified category to satisfy the accuracy constraint.On the contrary,the smaller the value n is,the slower it will be for the specified category to satisfy the T(i,)= minisksjt(i,k)+T(k+1,j)),i<j; t(i,i), (8) i=j. accuracy constraint.This occurs during the ensemble sampling, when the major categories occupy most of the singleton slots,In Eq.(8),the value of T(i,j)is obtained by enumerating each while those minor categories cannot obtain enough samplings possible combination of t(i,k)and T(+1,j),and then getting in the singleton slots for accurate estimation of the tag size. the minimum value of t(i,)+T(k+1,j).By solving theto denote the variance of 𝑛ˆ. We rely on the following theorem to illustrate the accuracy of the estimator SE. Theorem 1: Let 𝛿𝑖 represent the variance of the estimator SE 𝑛ˆ𝑖, the load factor 𝜌 = 𝑛 𝑓 , then, 𝛿𝑖 = 𝑛𝑖 𝑛 ⋅ 𝑒𝜌 + 𝑛𝑖 − 1 𝑒𝜌 + 𝑛 − 1 ⋅ (𝛿 + 𝑛2) − 𝑛2 𝑖 . (7) Proof: See Appendix A. 2) Reducing the Variance through Repeated Tests: As the frame size for each query cycle has a maximum value, by estimating from the ensemble sampling within only one query cycle, the estimated tag size may not be accurate enough for the accuracy constraint. In this situation, multiple query cycles are essential to reduce the variance through repeated tests. Suppose the reader issues 𝑙 query cycles over the same set of categories, in regard to a specified category 𝐶𝑖, by utilizing the weighted statistical averaging method, the averaged tag size 𝑛ˆ𝑖 = ∑𝑙 𝑘=1 𝜔𝑘 ⋅ 𝑛ˆ𝑖,𝑘; here 𝜔𝑘 = 1 𝛿 ∑ 𝑖,𝑘 𝑙 𝑘=1 1 𝛿𝑖,𝑘 , 𝑛ˆ𝑖,𝑘 and 𝛿𝑖,𝑘 respectively denote the estimated tag size and variance for each cycle 𝑘. Then, the variance of 𝑛ˆ𝑖 is 𝜎2 𝑖 = ∑ 1 𝑙 𝑘=1 1 𝛿𝑖,𝑘 . Therefore, according to the accuracy constraint in the prob￾lem formulation, we rely on the following theorem to express this constraint in the form of the variance. Theorem 2: Suppose the variance of the averaged tag size 𝑛ˆ𝑖 is 𝜎2 𝑖 . The accuracy constraint is satisfied for a specified category 𝐶𝑖, as long as 𝜎2 𝑖 ≤ ( 𝜖 𝑍1−𝛽/2 )2 ⋅ 𝑛2 𝑖 , 𝑍1−𝛽/2 is the 1 − 𝛽 2 percentile for the standard normal distribution. Proof: See Appendix B. According to Theorem 2, we can verify if the accuracy con￾straint is satisfied for each category through directly checking the variance against the threshold ( 𝜖 𝑍1−𝛽/2 )2⋅𝑛2 𝑖 . If 1−𝛽 = 95%, then 𝑍1−𝛽/2 = 1.96. 3) Property of the Ensemble Sampling: According to The￾orem 1, the normalized variance of the SE estimator 𝜆𝑖 = 𝛿𝑖 𝑛𝑖 is equivalent to 𝜆𝑖 = 𝛿−𝑛⋅𝑒𝜌+𝑛 𝑒𝜌+𝑛−1 ⋅ 𝑛𝑖 𝑛 + (𝛿+𝑛2)(𝑒𝜌−1) 𝑛⋅(𝑒𝜌+𝑛−1) . Let 𝑎 = 𝛿−𝑛⋅𝑒𝜌+𝑛 𝑒𝜌+𝑛−1 , 𝑏 = (𝛿+𝑛2)(𝑒𝜌−1) 𝑛⋅(𝑒𝜌+𝑛−1) . Then, the normalized variance 𝜆𝑖 = 𝑎 ⋅ 𝑛𝑖 𝑛 + 𝑏. Since the SE estimator can utilize any estimator like [4][12][15] to estimate the overall tag size, then, without loss of generality, if we use the estimator in [4], we can prove that 𝑎 < 0 for any value of 𝑛 > 0,𝑓 > 0. This property applies to any estimator with variance smaller than 𝛿0 in ZE, which simply estimates the overall tag size based on the observed number of empty slots. According to Theorem 2, in order to satisfy the accuracy constraint, we should ensure that 𝜆𝑖 ≤ ( 𝜖 𝑍1−𝛽/2 )2 ⋅𝑛𝑖. As 𝑎 < 0 for all values of 𝑓, it infers that the larger the value 𝑛𝑖 is, the faster it will be for the specified category to satisfy the accuracy constraint. On the contrary, the smaller the value 𝑛𝑖 is, the slower it will be for the specified category to satisfy the accuracy constraint. This occurs during the ensemble sampling, when the major categories occupy most of the singleton slots, while those minor categories cannot obtain enough samplings in the singleton slots for accurate estimation of the tag size. C. Compute the Optimal Granularity for Ensemble Sampling As indicated in the above analysis, during a query cycle of the ensemble sampling, in order to achieve the accuracy requirement for all categories, the essential scanning time mainly depends on the category with the smallest tag size, as the other categories must still be involved in the query cycle until this category achieves the accuracy requirement. Therefore, we use the notion group to define a set of categories involved in a query cycle of the ensemble sampling. Hence, each cycle of ensemble sampling should be applied over an appropriate group, such that the variance of the tag sizes for the involved categories cannot be too large. In this way, all categories in the same group achieve the accuracy requirement with very close finishing time. In addition, according to Eq. (7), as the number of categories increases in the ensemble sampling, the load factor 𝜌 is increased, then the achieved accuracy for each involved category is reduced. Therefore, it is essential to compute an optimal granularity for the group in regard to the reading performance. Suppose there exists 𝑚 categories in total, the objective is to divide them into 𝑑(1 ≤ 𝑑 ≤ 𝑚) groups for ensemble sampling, such that the overall scanning time can be minimized while achieving the accuracy requirement. For a specified group, in order for all involved categories to satisfy the accuracy requirement, it is essential to compute the required frame size for the category with the smallest tag size, say 𝑛𝑖. Let 𝑡𝑖 = ( 𝜖 𝑍1−𝛽/2 )2 ⋅ 𝑛𝑖, then, according to Theorem 2, we can compute the essential frame size 𝑓 such that 𝜆𝑖(𝑓) ≤ 𝑡𝑖. Assume that the inter-cycle overhead is 𝜏𝑐, and the average time interval per slot is 𝜏𝑠. Therefore, if 𝑓 ≤ 𝑓𝑚𝑎𝑥, then the total scanning time 𝑇 = 𝑓 ⋅ 𝜏𝑠 + 𝜏𝑐. Otherwise, if the final estimate is the average of 𝑟 independent experiments each with an estimator variance of 𝜆𝑖(𝑓𝑚𝑎𝑥), then the variance of the average is 𝜆𝑖(𝑓𝑚𝑎𝑥) 𝑟 . Hence, if we want the final variance to be 𝑡𝑖, then 𝑟 should be 𝜆𝑖(𝑓𝑚𝑎𝑥) 𝑡𝑖 , the total scanning time is 𝑇 = (𝑓𝑚𝑎𝑥 ⋅ 𝜏𝑠 + 𝜏𝑐) ⋅ 𝑟. We propose a dynamic programming-based algorithm to compute the optimal granularity for ensemble sampling. As￾sume that currently there are 𝑚 categories, ranked in non￾increasing order, according to the estimated tag size, e.g., 𝐶1, 𝐶2, ..., 𝐶𝑚. We need to cut the ranked categories into one or more continuous groups for ensemble sampling. In regard to a single group consisting of categories from 𝐶𝑖 to 𝐶𝑗 , we define 𝑡(𝑖, 𝑗) as the essential scanning time for ensemble sampling, which is computed in the same way as aforementioned 𝑇. Fur￾thermore, we define 𝑇(𝑖, 𝑗) as the minimum overall scanning time over the categories from 𝐶𝑖 to 𝐶𝑗 among various grouping strategies. Then, the recursive expression of 𝑇(𝑖, 𝑗) is shown in Eq.(8). 𝑇(𝑖, 𝑗) = { min𝑖≤𝑘≤𝑗{𝑡(𝑖, 𝑘) + 𝑇(𝑘 + 1, 𝑗)}, 𝑖<𝑗; 𝑡(𝑖, 𝑖), 𝑖 = 𝑗. (8) In Eq. (8), the value of 𝑇(𝑖, 𝑗) is obtained by enumerating each possible combination of 𝑡(𝑖, 𝑘) and 𝑇(𝑘+1, 𝑗), and then getting the minimum value of 𝑡(𝑖, 𝑘) + 𝑇(𝑘 + 1, 𝑗). By solving the