Finding duplicates in a data stream

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Finding duplicates in a data stream

Full text

Pdf (508 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms table of contents

New York, New York

Pages 402-411

Year of Publication: 2009

Authors

Parikshit Gopalan	University of Washington & Microsoft Research SVC
Jaikumar Radhakrishnan	TIFR, Mumbai

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 131, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

Given a data stream of length n over an alphabet [m] where n > m, we consider the problem of finding a duplicate in a single pass. We give a randomized algorithm for this problem that uses O((log m)³) space. This answers a question of Muthukrishnan [Mut05] and Tarui [Tar07], who asked if this problem could be solved using sub-linear space and one pass over the input. Our algorithm solves the more general problem of finding a positive frequency element in a stream given by frequency updates where the sum of all frequencies is positive. Our main tool is an Isolation Lemma that reduces this problem to the task of detecting and identifying a Dictatorial variable in a Boolean halfspace. We present various relaxations of the condition n > m, under which one can find duplicates efficiently.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, v.58 n.1, p.137-147, Feb. 1999 [doi>10.1006/jcss.1997.1545]
	2	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]
	3	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]
	4	B. Chor , O. Goldreich, On the power of two-point based sampling, Journal of Complexity, v.5 n.1, p.96-106, March 1989 [doi>10.1016/0885-064X(89)90015-0]
	5	{Cha08} M. Charikar. Top-k frequent item maintenance over streams. Survey article, 2008.
	6	{CKS03} A. Chakrabarti, S. Khot, and X. Sun. Near-optimal lower bounds on the multiparty communication complexity of set-disjointness. In Proc. 18^th IEEE Conference on Computational Complexity, pages 107--117, 2003.
	7	Fan Deng , Davood Rafiei, Approximately detecting duplicates for streaming data using stable bloom filters, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142477]
	8	{For05} L. Fortnow. Finding duplicates: Post on the Computational Complexity weblog, March 4^th 2005.
	9	Surajit Chaudhuri , Venkatesh Ganti , Rajeev Motwani, Robust Identification of Fuzzy Duplicates, Proceedings of the 21st International Conference on Data Engineering, p.865-876, April 05-08, 2005 [doi>10.1109/ICDE.2005.125]
	10	Piotr Indyk, Stable distributions, pseudorandom generators, embeddings, and data stream computation, Journal of the ACM (JACM), v.53 n.3, p.307-323, May 2006 [doi>10.1145/1147954.1147955]
	11	Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
	12	Bala Kalyanasundaram , Georg Schintger, The probabilistic communication complexity of set intersection, SIAM Journal on Discrete Mathematics, v.5 n.4, p.545-557, Nov. 1992 [doi>10.1137/0405044]
	13	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]
	14	{Mut05} S. Muthukrishnan. Data Streams: Algorithms and Applications. Now Publishers Inc., 2005.
	15	{Nis92} N. Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449--461, 1992.
	16	A. A. Razborov, On the distributional complexity of disjointness, Theoretical Computer Science, v.106 n.2, p.385-390, Dec. 1992 [doi>10.1016/0304-3975(92)90260-M]
	17	{Tar07} J. Tarui. Finding a duplicate and a missing item in a stream. In TAMC, pages 128--135, 2007.