|Table of Contents|

RFID duplicate removing algorithm based on temporal-spatial Bloom filter


Research Field:
Publishing date:


RFID duplicate removing algorithm based on temporal-spatial Bloom filter
Wang Yongli1Wang Chuan1Jiang Xiaohui1Zhang Gongxuan1Sun Shujie2
1.School of Computer Science and Engineering,NUST,Nanjing 210094,China; 2.Third Mine Pusilian,Seventh Oil Extraction Plant,Daqing 163517,China
Bloom filter radio frequency identification redundant data integer array bit array memory space utilization false positive errors false negative errors
Aiming at the problem of huge amounts of duplicate data caused by the inherent unreliability of radio frequency identification(RFID),a redundant data filtering algorithm is proposed based on temporal-spatial Bloom filter.A great deal of RFID data are dealt every time using a limited memory.Integer array is used instead of bit array,and the memory space consumption is times of the tag length before.Compared with the traditional Bloom filter,the algorithm proposed here has good space utilization.The problem of traditional Bloom filter that it can't deal with a mass of real-time data flow is overcomed by the algorithm proposed here.False positive errors are removed,false negative errors are minimized by setting appropriate parameters.False negative errors are related to the specific application and filter settings specifically.Experimental results verify the effectiveness of the proposed algorithm.


[1] 陆宝春,丁日春,陈吉朋.基于自动分组排列的电子标签防碰撞算法[J].南京理工大学学报,2012,36(1):122-126.
Lu Baochun,Ding Richun,Chen Jipeng.Electronic tag anti-collision algorithm based on auto-grouping arrangement[J].Journal of Nanjing University of Science and Technology,2012,36(1):122-126.
[2]Baba A I,Lu Hua,Xie X.Spatio-temporal data cleansing for indoor RFID tracking data[A].2013 IEEE 14th International Conference on Mobile Date Management(MDM)[C].Milan,Italy:IEEE,2013:187-196.
[3]Mahdin H.A review on Bloom filter based approaches for RFID data cleaning[A].Proceedings of the First International Conference on Advanced Data and Information Engineering[C].Kuala Lumpur,Malaysia:Springer Singapore,2014:79-86.
[4]Jeffery S R,Alonso G,Franklin M J,et al.A pipelined framework for online cleaning of sensor data streams[A].Proceedings of the 22nd International Conference on Data Engineering(ICDE'06)[C].Atlanta,GA,USA:IEEE,2006:1-140.
[5]Bai Y,Wang F,Liu P.Efficiently filtering RFID data streams[A].Proceedings of the 32nd International Conference on Very Large Data Bases[C].Seoul,Korea:Springer Verlag,2006:50-57.
[6]Carbunar B,Ramanathan M K,Koyuturk M,et al.Redundant reader elimination in RFID systems[A].2005 Second Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks[C].Anchorage,AK,USA:IEEE Computer Society,2005:176-184.
[7]Lee C H,Chung C W.An approximate duplicate elimination in RFID data streams[J].Data and Knowledge Engineering,2011,70(12):1070-1087.
[8]Bloom B H.Space/time trade-offs in hash coding with allowable errors[J].Communications of the ACM,1970,13(7):422-426.
[9]Metwally A,Agrawal D,El Abbadi A.Duplicate detection in click streams[A].Proceedings of the 14th International Conference on World Wide Web[C].New York,USA:ACM,2005:12-21.
[10]Deng Fan,Rafiei D.Approximately detecting duplicates for streaming data using stable Bloom filters[A].Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data[C].Chicago,USA:ACM,2006:25-36.
[11]Wang Xiaowei,Zhang Qiang,Jia Yan.Efficiently filtering duplicates over distributed data streams[A].Proceedings of the 2008 International Conference on Computer Science and Software Engineering[C].Anchorage,AK,USA:IEEE Computer Society,2008:631-634.
Han Jingyu,Xu Lizhen,Dong Yisheng.An overview of data quality research[J].Computer Science,2008,35(2):1-5,12.
[13]Mitzenmacher M.Compressed Bloom filters[J].IEEE/ACM Transactions on Networking(TON),2002,10(5):604-612.
[14]Peiya F W.Temporal management of RFID data[A].Proceedings of the 31st International Conference on Very Large Data Bases[C].Trondheim,Norway:Springer Verlag,2005:1128-1139.
[15]Jeffery S R,Franklin M J.Adaptive cleaning for RFID data streams[A].Proceedings of the 32nd International Conference on Very Large Data Bases[C].Seoul,Korea:Springer Verlag,2006:163-174.


Last Update: 2015-06-30