Approximately detecting duplicates for streaming data using stable bloom filters

ABSTRACT

Traditional duplicate elimination techniques are not applicable to many data stream applications. In general, precisely eliminating duplicates in an unbounded data stream is not feasible in many streaming scenarios. Therefore, we target at approximately eliminating duplicates in streaming environments given a limited space. Based on a well-known bitmap sketch, we introduce a data structure, Stable Bloom Filter, and a novel and simple algorithm. The basic idea is as follows: since there is no way to store the whole history of the stream, SBF continuously evicts the stale information so that SBF has room for those more recent elements. After finding some properties of SBF analytically, we show that a tight upper bound of false positive rates is guaranteed. In our empirical study, we compare SBF to alternative methods. The results show that our method is superior in terms of both accuracy and time effciency when a fixed small space and an acceptable false positive rate are given.

REFERENCES

• 1: [1] R. Ananthakrishna, S. Chaudhuri, and V. Ganti. Eliminating fuzzy duplicates in data warehouses. In Proc. of VLDB, 2002.
• 2: [2] Internet Archive. http://www.archive.org/.
• 3: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 4: Brian Babcock , Mayur Datar , Rajeev Motwani, Load Shedding for Aggregation Queries over Data Streams, Proceedings of the 20th International Conference on Data Engineering, p.350, March 30-April 02, 2004
• 5: [5] F. Baboescu, S. Singh, and G. Varghese. Packet classification for core routers: Is there an alternative to cams? In Proc. of INFOCOMM, 2003.
• 6: Mikhail Bilenko , Raymond J. Mooney, Adaptive duplicate detection using learnable string similarity measures, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956759]
• 7: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 8: Andrei Z. Broder , Marc Najork , Janet L. Wiener, Efficient URL caching for world wide web crawling, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775247]
• 9: [9] D. Carney, U. Cetintemel, M. Cherniack, C. Convey, S. Lee, G. Seidman, M. Stonebraker, N. Tatbul, and S. B. Zdonik. Monitoring streams - a new class of data management applications. In Proc. of VLDB, 2002.
• 10: [10] S. Chandrasekaran, O. Cooper, A. Deshpande, M. J. Franklin, J. M. Hellerstein, W. Hong, S. Krishnamurthy, S. Madden, V. Raman, F. Reiss, and M. A. Shah. Telegraphcq: Continuous dataflow processing for an uncertain world. In Proc. of CIDR, 2003.
• 11: Surajit Chaudhuri , Venkatesh Ganti , Rajeev Motwani, Robust Identification of Fuzzy Duplicates, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.865-876, April 05-08, 2005 [doi>10.1109/ICDE.2005.125]
• 12: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.379-390, May 15-18, 2000, Dallas, Texas, United States
• 13: Edith Cohen , Martin Strauss, Maintaining time-decaying stream aggregates, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.223-233, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773175]
• 14: Saar Cohen , Yossi Matias, Spectral bloom filters, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872787]
• 15: Graham Cormode , Mayur Datar , Piotr Indyk , S. Muthukrishnan, Comparing Data Streams Using Hamming Norms (How to Zero In), IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.529-540, March 2003 [doi>10.1109/TKDE.2003.1198388]
• 16: Chuck Cranor , Theodore Johnson , Oliver Spataschek , Vladislav Shkapenyuk, Gigascope: a stream database for network applications, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872838]
• 17: [17] C. Estan and G. Varghese. Data streaming in computer networks. In Proc. of Workshop on Management and Processing of Data Streams (MPDS) in cooperation with SIGMOD/PODS, 2003.
• 18: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area web cache sharing protocol, IEEE/ACM Transactions on Networking (TON), v.8 n.3, p.281-293, June 2000 [doi>10.1109/90.851975]
• 19: Philippe Flajolet , G. Nigel Martin, Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences, v.31 n.2, p.182-209, Sept. 1985 [doi>10.1016/0022-0000(85)90041-8]
• 20: Hector Garcia-Molina , Jennifer Widom , Jeffrey D. Ullman, Database System Implementation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 21: Allan Heydon , Marc Najork, Mercator: A scalable, extensible Web crawler, World Wide Web, v.2 n.4, p.219-229, 1999 [doi>10.1023/A:1019213109274]
• 22: [22] Cisco System Inc. Cisco network accounting services. http://www.cisco.com/warp/public/cc/pd/iosw/ prodlit/nwact_wp.pdf, 2002.
• 23: [23] G. S. Manku and R. Motwani. Approximate frequency counts over data streams. In Proc. of VLDB, 2002.
• 24: Ahmed Metwally , Divyakant Agrawal , Amr El Abbadi, Duplicate detection in click streams, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060753]
• 25: Michael Mitzenmacher, Compressed bloom filters, IEEE/ACM Transactions on Networking (TON), v.10 n.5, p.604-612, October 2002 [doi>10.1109/TNET.2002.803864]
• 26: Themistoklis Palpanas , Michail Vlachos , Eamonn Keogh , Dimitrios Gunopulos , Wagner Truppel, Online Amnesic Approximation of Streaming Time Series, Proceedings of the 20th International Conference on Data Engineering, p.338, March 30-April 02, 2004
• 27: [27] M. O. Rabin. Fingerprinting by random polynomials. Technical Report TR-15-81, Center for Research in Computing Technology, Harvard University, 1981.
• 28: [28] N. Tatbul, U. Cetintemel, S. Zdonik, M. Cherniack, and M. Stonebraker. Load shedding in a data stream manager. In Proc. of VLDB, 2003.
• 29: [29] P. A. Tucker, D. Maier, and T. Sheard. Applying punctuation schemes to queries over continuous data streams. IEEE Data Eng. Bull., 26(1):33-40, 2003.
• 30: Melanie Weis , Felix Naumann, DogmatiX tracks down duplicates in XML, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066207]
• 31: Kyu-Young Whang , Brad T. Vander-Zanden , Howard M. Taylor, A linear-time probabilistic counting algorithm for database applications, ACM Transactions on Database Systems (TODS), v.15 n.2, p.208-229, June 1990 [doi>10.1145/78922.78925]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.m Miscellaneous

General Terms:
Algorithms

Keywords:
algorithms, approximation, data stream, duplicate detection