essential to verify the categories for accuracy;then,as the value [15]H.Han,B.Sheng.C.C.Tan,Q.Li,W.Mao,and S.Lu,"Counting rfid of k further increases,more qualified categories with large tag tags efficiently and anonymously,"in Proc.of INFOCOM,2010. [16]M.Fang,N.Shivakumar,H.Garcia-Molina,R.Motwani,and J.D. sizes can be quickly wiped out in the threshold estimation, Ullman,"Computing iceberg queries efficiently,"in Proc.of the 24th thus fewer slots are required in the threshold estimation,and VLDB Conf.1998. the overall scanning time is decreased.In Fig.3(d),we eval- [17]L.Xie.H.Han,Q.Li.J.Wu,and S.Lu."Efficiently collect- uate the convergence for estimating the threshold t.We set ing histograms over rfid tags,"Nanjing University,Tech.Rep.,2013, http://cs.nju.edu.cn/lxie/publication/histogram.pdf. m=200,μ=500，o=200,k=20.We observe that the APPENDIX width of the range [t,t,i.e.,g,is continuously decreasing as A:Proof of Theorem 1 the scanning time increases.When the scanning time reaches Proof:According to the definitionE(= 1.8 x 105,the value of g is below the required threshold in the dash line,then the iteration ends. E().E(2)=E().Despite that n.n the relationship between ns and ns.i is rather weak as long as m is X.CONCLUSION fairly large.Hence we can assume ns.i and ns are independent We believe this is the first paper considering the problem of of each other.Then,according to the property of independence, collecting histograms over RFID tags.Based on the ensemble E@)==兴，E()=密.Then,as it can be sampling method,we respectively propose effective solutions proved that for the basic histogram collection,iceberg query problem and top-k query problem.Simulation results show that our solution E(n)=1-3-1.n+f-11-3》-2n2-m achieves much better performance than others. E(n2=(1-F)m-1.n+ 1-子)-6-n, f-1 ACKNOWLEDGMENTS we have This work is supported in part by National Natural Science Foundation of China under Grant No.61100196.61073028. a2)=%.1+1-点)m-2.(m-1） 61321491,91218302;JiangSu Natural Science Foundation un- n1+(1-吉)m-2·(n-1) der Grant No.BK2011559.Qun Li is supported in part by US NSF grants CNS-1117412,CNS-1320453,and CAREER ≈.1+e-p(ni-1) n1+e-p.(n-1) Award CNS-0747108.Jie Wu is supported in part by US NSF grants ECCS 1231461,ECCS 1128209,CNS 1138963,CNS Thus,6=E(2)-E2()=E(;2.2)-n2.Note that 1065444.and CC℉1028167 n is estimated from the estimator which relies on the number of empty/singleton/collison slots as well as the frame size f, REFERENCES while is equal to ,i.e.,the proportion that the category [1]C.Qian,Y.Liu,H.-L.Ngan,and L.M.Ni,"Asap:Scalable identification Ci occupies in the singleton slots.Therefore,we can assume the and counting for contactless rfid systems,"in Proc.of /EEE ICDCS,2010. [2]M.Shahzad and A.X.Liu,"Every bit counts fast and scalable rfid independence between a;and n,then 6i=E().E(n2)-n2. estimation,"in Proc.of MobiCom,2012. As the variance 6 E(n2)-E()2 and E(n)=n,thus [3]Y.Zheng and M.Li,"Fast tag searching protocol for large-scale rfid E(n2)=6+n2.Therefore, systems,"in Proc.of ICNP,2011. [4]M.Kodialam and T.Nandagopal."Fast and reliable estimation schemes d:=.ep+n-1 in rfid systems,"in Proc.of MobiCom,2006. (6+n2)-n2 n ep+n-1 [5]B.Sheng.C.C.Tan,Q.Li,and W.Mao,"Finding popular categoried for RFID tags,"in Proc.of ACM MobiHoc,2008. ◆ [6]Y.E.Ioannidis and V.Poosala,"Histogram-based approximation of set- B:Proof of Theorem 2 valued query answers,"in Proc.of the 25th VLDB Conference,1999. Proof:Suppose identical frame sizes are used for each [7]S.Tang.J.Yuan,X.Y.Li,G.Chen,Y.Liu,and J.Zhao,"Raspberry:A stable reader activation scheduling protocol in multi-reader rfid systems," query cycle in the repeated tests.Then,in regard to a specified in Proc.of ICNP,2009. category Ci,the series of estimated tag sizes [nik for I query [8]L.Yang.J.Han,Y.Qi,C.Wang.T.Gu,and Y.Liu,"Season:Shelving cycles are independent and identically distributed.Since the interference and joint identification in large-scale rfid systems,"in Proc. of INFOCOM,2011. variance 6i.is equal for each query cycle,according to the [9]S.Chen,M.Zhang,and B.Xiao,"Efficient information collection weighted statistical averaging method,the estimated tag size protocols for sensor-augmented rfid networks,"in Proc.of INFOCOM. is ni= 2011. .As the expected value and standard [10]Y.Qiao,S.Chen,T.Li,and S.Chen,"Energy-efficient polling protocols deviation for the averaged value ni are respectively ni and oi, in rfid systems,"in Proc.of MobiHoc,2011. then according to the Central Limit Theorem,X=n is [11]T.Li.S.Wu,S.Chen,and M.Yang."Energy efficient algorithms for the asymptotically normal with mean 0 and variance 1,that is,X rfid estimation problem,"in Proc.of INFOCOM.2010. [12]W.Chen,"An accurate tag estimate method for improving the perfor- satisfies the standard normal distribution. mance of an rfid anticollision algorithm based on dynamic frame length Therefore,the definition of the accuracy constraint is equiva- aloha."IEEE Transactions on Automation Science and Engineering, lent to:Pr-e≤-严≤s]≥1-B.We use Z1-B/2to vol.6,no.1,pp.9-15,2009. 0。 [13]W.Luo,Y.Qiao,and S.Chen,"An efficient protocol for rfid multigroup denote the 1-2 percentile for the standard normal distribution. threshold-based classification,"in Proc.of INFOCOM,2013. Hence,in order to satisfy the accuracy constraint,it is essential [14]M.Buettner and D.Wetherall,"An empirical study of uhf rfid perfor- mance,"in Proc.of MobiCom,2008. to ensure≥Zi-a2,that is,.a≤(z-aa2.nessential to verify the categories for accuracy; then, as the value of 𝑘 further increases, more qualified categories with large tag sizes can be quickly wiped out in the threshold estimation, thus fewer slots are required in the threshold estimation, and the overall scanning time is decreased. In Fig.3(d), we eval￾uate the convergence for estimating the threshold 𝑡. We set 𝑚 = 200, 𝜇 = 500, 𝜎 = 200, 𝑘 = 20. We observe that the width of the range [˜𝑡,𝑡 ¯], i.e., 𝑔, is continuously decreasing as the scanning time increases. When the scanning time reaches 1.8 × 105, the value of 𝑔 is below the required threshold in the dash line, then the iteration ends. X. CONCLUSION We believe this is the first paper considering the problem of collecting histograms over RFID tags. Based on the ensemble sampling method, we respectively propose effective solutions for the basic histogram collection, iceberg query problem and top-𝑘 query problem. Simulation results show that our solution achieves much better performance than others. ACKNOWLEDGMENTS This work is supported in part by National Natural Science Foundation of China under Grant No. 61100196, 61073028, 61321491, 91218302; JiangSu Natural Science Foundation un￾der Grant No. BK2011559. Qun Li is supported in part by US NSF grants CNS-1117412, CNS-1320453, and CAREER Award CNS-0747108. Jie Wu is supported in part by US NSF grants ECCS 1231461, ECCS 1128209, CNS 1138963, CNS 1065444, and CCF 1028167. REFERENCES [1] C. Qian, Y. Liu, H.-L. Ngan, and L. M. Ni, “Asap: Scalable identification and counting for contactless rfid systems,” in Proc. of IEEE ICDCS, 2010. [2] M. Shahzad and A. X. Liu, “Every bit counts - fast and scalable rfid estimation,” in Proc. of MobiCom, 2012. [3] Y. Zheng and M. Li, “Fast tag searching protocol for large-scale rfid systems,” in Proc. of ICNP, 2011. [4] M. Kodialam and T. Nandagopal, “Fast and reliable estimation schemes in rfid systems,” in Proc. of MobiCom, 2006. [5] B. Sheng, C. C. Tan, Q. Li, and W. Mao, “Finding popular categoried for RFID tags,” in Proc. of ACM MobiHoc, 2008. [6] Y. E. Ioannidis and V. Poosala, “Histogram-based approximation of set￾valued query answers,” in Proc. of the 25th VLDB Conference, 1999. [7] S. Tang, J. Yuan, X. Y. Li, G. Chen, Y. Liu, and J. Zhao, “Raspberry: A stable reader activation scheduling protocol in multi-reader rfid systems,” in Proc. of ICNP, 2009. [8] L. Yang, J. Han, Y. Qi, C. Wang, T. Gu, and Y. Liu, “Season: Shelving interference and joint identification in large-scale rfid systems,” in Proc. of INFOCOM, 2011. [9] S. Chen, M. Zhang, and B. Xiao, “Efficient information collection protocols for sensor-augmented rfid networks,” in Proc. of INFOCOM, 2011. [10] Y. Qiao, S. Chen, T. Li, and S. Chen, “Energy-efficient polling protocols in rfid systems,” in Proc. of MobiHoc, 2011. [11] T. Li, S. Wu, S. Chen, and M. Yang, “Energy efficient algorithms for the rfid estimation problem,” in Proc. of INFOCOM, 2010. [12] W. Chen, “An accurate tag estimate method for improving the perfor￾mance of an rfid anticollision algorithm based on dynamic frame length aloha,” IEEE Transactions on Automation Science and Engineering, vol. 6, no. 1, pp. 9–15, 2009. [13] W. Luo, Y. Qiao, and S. Chen, “An efficient protocol for rfid multigroup threshold-based classification,” in Proc. of INFOCOM, 2013. [14] M. Buettner and D. Wetherall, “An empirical study of uhf rfid perfor￾mance,” in Proc. of MobiCom, 2008. [15] H. Han, B. Sheng, C. C. Tan, Q. Li, W. Mao, and S. Lu, “Counting rfid tags efficiently and anonymously,” in Proc. of INFOCOM, 2010. [16] M. Fang, N. Shivakumar, H. Garcia-Molina, R. Motwani, and J. D. Ullman, “Computing iceberg queries efficiently,” in Proc. of the 24th VLDB Conf, 1998. [17] L. Xie, H. Han, Q. Li, J. Wu, and S. Lu, “Efficiently collect￾ing histograms over rfid tags,” Nanjing University, Tech. Rep., 2013, http://cs.nju.edu.cn/lxie/publication/histogram.pdf. APPENDIX A: Proof of Theorem 1 Proof: According to the definition 𝛼ˆ𝑖 = 𝑛𝑠,𝑖 𝑛𝑠 , 𝐸(𝛼ˆ𝑖) = 𝐸( 𝑛𝑠,𝑖 𝑛𝑠 ), 𝐸(𝛼ˆ𝑖 2 ) = 𝐸( 𝑛2 𝑠,𝑖 𝑛2 𝑠 ). Despite that 𝑛𝑠 = ∑𝑚 𝑖=1 𝑛𝑠,𝑖, the relationship between 𝑛𝑠 and 𝑛𝑠,𝑖 is rather weak as long as 𝑚 is fairly large. Hence we can assume 𝑛𝑠,𝑖 and 𝑛𝑠 are independent of each other. Then, according to the property of independence, 𝐸(𝛼ˆ𝑖) = 𝐸(𝑛𝑠,𝑖) 𝐸(𝑛𝑠) = 𝑛𝑖 𝑛 , 𝐸(𝛼ˆ𝑖 2 ) = 𝐸(𝑛2 𝑠,𝑖) 𝐸(𝑛2 𝑠) . Then, as it can be proved that 𝐸(𝑛2 𝑠) = (1 − 1 𝑓 ) 𝑛−1 ⋅ 𝑛 + 𝑓 − 1 𝑓 (1 − 2 𝑓 ) 𝑛−2(𝑛2 − 𝑛), 𝐸(𝑛2 𝑠,𝑖) = (1 − 1 𝑓 ) 𝑛−1 ⋅ 𝑛𝑖 + 𝑓 − 1 𝑓 (1 − 2 𝑓 ) 𝑛−2(𝑛2 𝑖 − 𝑛𝑖). we have 𝐸(𝛼ˆ𝑖 2 ) = 𝑛𝑖 𝑛 ⋅ 1 + (1 − 1 𝑓−1 )𝑛−2 ⋅ (𝑛𝑖 − 1) 1 + (1 − 1 𝑓−1 )𝑛−2 ⋅ (𝑛 − 1) ≈ 𝑛𝑖 𝑛 ⋅ 1 + 𝑒−𝜌 ⋅ (𝑛𝑖 − 1) 1 + 𝑒−𝜌 ⋅ (𝑛 − 1) . Thus, 𝛿𝑖 = 𝐸(𝑛ˆ𝑖 2 ) − 𝐸2(𝑛ˆ𝑖) = 𝐸(𝛼ˆ𝑖 2 ⋅ 𝑛ˆ2) − 𝑛2 𝑖 . Note that 𝑛ˆ is estimated from the estimator which relies on the number of empty/singleton/collison slots as well as the frame size 𝑓, while 𝛼ˆ𝑖 is equal to 𝑛𝑠,𝑖 𝑛𝑠 , i.e., the proportion that the category 𝐶𝑖 occupies in the singleton slots. Therefore, we can assume the independence between 𝛼ˆ𝑖 and 𝑛ˆ, then 𝛿𝑖 = 𝐸(𝛼ˆ𝑖 2 )⋅𝐸(𝑛ˆ2)−𝑛2 𝑖 . As the variance 𝛿 = 𝐸(𝑛ˆ2) − 𝐸(𝑛ˆ)2 and 𝐸(𝑛ˆ) = 𝑛, thus 𝐸(𝑛ˆ2) = 𝛿 + 𝑛2. Therefore, 𝛿𝑖 = 𝑛𝑖 𝑛 ⋅ 𝑒𝜌 + 𝑛𝑖 − 1 𝑒𝜌 + 𝑛 − 1 ⋅ (𝛿 + 𝑛2) − 𝑛2 𝑖 . B: Proof of Theorem 2 Proof: Suppose identical frame sizes are used for each query cycle in the repeated tests. Then, in regard to a specified category 𝐶𝑖, the series of estimated tag sizes {𝑛ˆ𝑖,𝑘} for 𝑙 query cycles are independent and identically distributed. Since the variance 𝛿𝑖,𝑘 is equal for each query cycle, according to the weighted statistical averaging method, the estimated tag size is 𝑛ˆ𝑖 = 1 𝑙 ∑𝑙 𝑘=1 𝑛ˆ𝑖,𝑘. As the expected value and standard deviation for the averaged value 𝑛ˆ𝑖 are respectively 𝑛𝑖 and 𝜎𝑖, then according to the Central Limit Theorem, 𝑋 = 𝑛ˆ𝑖−𝑛𝑖 𝜎𝑖 is asymptotically normal with mean 0 and variance 1, that is, 𝑋 satisfies the standard normal distribution. Therefore, the definition of the accuracy constraint is equiva￾lent to: 𝑃 𝑟[ −𝜖⋅𝑛𝑖 𝜎𝑖 ≤ 𝑛ˆ𝑖−𝑛𝑖 𝜎𝑖 ≤ 𝜖⋅𝑛𝑖 𝜎𝑖 ] ≥ 1 − 𝛽. We use 𝑍1−𝛽/2 to denote the 1− 𝛽 2 percentile for the standard normal distribution. Hence, in order to satisfy the accuracy constraint, it is essential to ensure 𝜖⋅𝑛𝑖 𝜎𝑖 ≥ 𝑍1−𝛽/2, that is, 𝜎2 𝑖 ≤ ( 𝜖 𝑍1−𝛽/2 )2 ⋅ 𝑛2 𝑖