A simple algorithm for finding frequent elements in streams and bags

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A simple algorithm for finding frequent elements in streams and bags

Full text

Pdf (79 KB)

Source

ACM Transactions on Database Systems (TODS) archive
Volume 28 , Issue 1 (March 2003) table of contents

Pages: 51 - 55

Year of Publication: 2003

ISSN:0362-5915

Authors

Richard M. Karp	International Computer Science Institute and University of California, Berkeley, California
Scott Shenker	International Computer Science Institute and University of California, Berkeley, California
Christos H. Papadimitriou	University of California, Berkeley, California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 29, Downloads (12 Months): 180, Citation Count: 51

Additional Information:

abstract references cited by index terms collaborative colleagues

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

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/762471.762473 What is a DOI?

ABSTRACT

We present a simple, exact algorithm for identifying in a multiset the items with frequency more than a threshold θ. The algorithm requires two passes, linear time, and space 1/θ. The first pass is an on-line algorithm, generalizing a well-known algorithm for finding a majority element, for identifying a set of at most 1/θ items that includes, possibly among others, all items with frequency greater than θ.

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, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
	2	Kevin Beyer , Raghu Ramakrishnan, Bottom-up computation of sparse and Iceberg CUBE, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.359-370, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	3	Moses Charikar , Kevin Chen , Martin Farach-Colton, Finding Frequent Items in Data Streams, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.693-703, July 08-13, 2002
	4	Erik D. Demaine , Alejandro López-Ortiz , J. Ian Munro, Frequency Estimation of Internet Packet Streams with Limited Space, Proceedings of the 10th Annual European Symposium on Algorithms, p.348-360, September 17-21, 2002
	5	Cristian Estan , George Varghese, New directions in traffic measurement and accounting, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505212]
	6	Min Fang , Narayanan Shivakumar , Hector Garcia-Molina , Rajeev Motwani , Jeffrey D. Ullman, Computing Iceberg Queries Efficiently, Proceedings of the 24rd International Conference on Very Large Data Bases, p.299-310, August 24-27, 1998
	7	Phillip B. Gibbons , Yossi Matias, Synopsis data structures for massive data sets, External memory algorithms, American Mathematical Society, Boston, MA, 1999
	8	Pan, R., Breslau, L., Prabhakar, B., and Shenker, S. Approximate fairness through differential dropping. preprint, 2001.

CITED BY 52

	Graham Cormode , S. Muthukrishnan, What's hot and what's not: tracking most frequent items dynamically, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.296-306, June 09-11, 2003, San Diego, California
	Abhishek Kumar , Jun (Jim) Xu , Li Li , Jia Wang, Space-code bloom filter for efficient traffic flow measurement, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA
	Cheqing Jin , Weining Qian , Chaofeng Sha , Jeffrey X. Yu , Aoying Zhou, Dynamically maintaining frequent items over a data stream, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA
	Cristian Estan , George Varghese, New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice, ACM Transactions on Computer Systems (TOCS), v.21 n.3, p.270-313, August 2003
	Moses Charikar , Kevin Chen , Martin Farach-Colton, Finding frequent items in data streams, Theoretical Computer Science, v.312 n.1, p.3-15, 26 January 2004
	L. K. Lee , H. F. Ting, Maintaining significant stream statistics over sliding windows, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.724-732, January 22-26, 2006, Miami, Florida
	Amitabha Bagchi , Amitabh Chaudhary , David Eppstein , Michael T. Goodrich, Deterministic sampling and range counting in geometric data streams, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Graham Cormode , Theodore Johnson , Flip Korn , S. Muthukrishnan , Oliver Spatscheck , Divesh Srivastava, Holistic UDAFs at streaming speeds, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	Arvind Arasu , Gurmeet Singh Manku, Approximate counts and quantiles over sliding windows, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
	Hua-Fu Li , Suh-Yin Lee , Man-Kwan Shan, On mining webclick streams for path traversal patterns, Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, May 19-21, 2004, New York, NY, USA
	Graham Cormode , S. Muthukrishnan, What's hot and what's not: tracking most frequent items dynamically, ACM Transactions on Database Systems (TODS), v.30 n.1, p.249-278, March 2005
	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
	Xiaogang Li , Gagan Agrawal, Efficient evaluation of XQuery over streaming data, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	John Hershberger , Nisheeth Shrivastava , Subhash Suri , Csaba D. Tóth, Space complexity of hierarchical heavy hitters in multi-dimensional data streams, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
	Naga K. Govindaraju , Nikunj Raghuvanshi , Dinesh Manocha, Fast and approximate stream mining of quantiles and frequencies using graphics processors, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Nan Jiang , Le Gruenwald, Research issues in data stream association rule mining, ACM SIGMOD Record, v.35 n.1, p.14-19, March 2006
	Graham Cormode , S. Muthukrishnan, What's new: finding significant differences in network data streams, IEEE/ACM Transactions on Networking (TON), v.13 n.6, p.1219-1232, December 2005
	Hua-Fu Li , Suh-Yin Lee , Man-Kwan Shan, DSM-PLW: single-pass mining of path traversal patterns over streaming web click-sequences, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.10, p.1474-1487, 14 July 2006
	Qin Zhang , Feifei Li , Ke Yi, Finding frequent items in probabilistic data, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
	Peter J. Desnoyers , Prashant Shenoy, Hyperion: high volume stream archival for retrospective querying, 2007 USENIX Annual Technical Conference on Proceedings of the USENIX Annual Technical Conference, p.1-14, June 17-22, 2007, Santa Clara, CA
	Qi (George) Zhao , Mitsunori Ogihara , Haixun Wang , Jun (Jim) Xu, Finding global icebergs over distributed data sets, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	Ahmed Metwally , Divyakant Agrawal , Amr El Abbadi, An integrated efficient solution for computing frequent and top-k elements in data streams, ACM Transactions on Database Systems (TODS), v.31 n.3, p.1095-1133, September 2006
	S. Muthukrishnan, Data streams: algorithms and applications, Foundations and Trends® in Theoretical Computer Science, v.1 n.2, p.117-236, August 2005
	L. K. Lee , H. F. Ting, A simpler and more efficient deterministic scheme for finding frequent items over sliding windows, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	Girish K. Palshikar , Mandar S. Kale , Manoj M. Apte, Association rules mining using heavy itemsets, Data & Knowledge Engineering, v.61 n.1, p.93-113, April, 2007
	Pierre-Alain Laur , Richard Nock , Jean-Emile Symphor , Pascal Poncelet, Mining evolving data streams for frequent patterns, Pattern Recognition, v.40 n.2, p.492-503, February, 2007
	Qi Zhao , Abhishek Kumar , Jun Xu, Joint data streaming and sampling techniques for detection of super sources and destinations, Proceedings of the Internet Measurement Conference 2005 on Internet Measurement Conference, p.7-7, October 19-21, 2005, Berkeley, CA
	Nagender Bandi , Ahmed Metwally , Divyakant Agrawal , Amr El Abbadi, Fast data stream algorithms using associative memories, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China
	Chedy Raïssi , Pascal Poncelet , Maguelonne Teisseire, Towards a new approach for mining frequent itemsets on data stream, Journal of Intelligent Information Systems, v.28 n.1, p.23-36, February 2007
	Graham Cormode , Flip Korn , S. Muthukrishnan , Divesh Srivastava, Finding hierarchical heavy hitters in data streams, Proceedings of the 29th international conference on Very large data bases, p.464-475, September 09-12, 2003, Berlin, Germany
	Amitabha Bagchi , Amitabh Chaudhary , David Eppstein , Michael T. Goodrich, Deterministic sampling and range counting in geometric data streams, ACM Transactions on Algorithms (TALG), v.3 n.2, p.16-es, May 2007
	Bo Sheng , Chiu Chiang Tan , Qun Li , Weizhen Mao, Finding popular categories for RFID tags, Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, May 26-30, 2008, Hong Kong, Hong Kong, China
	Xenofontas Dimitropoulos , Paul Hurley , Andreas Kind, Probabilistic lossy counting: an efficient algorithm for finding heavy hitters, ACM SIGCOMM Computer Communication Review, v.38 n.1, January 2008
	Frederic Raspall , Sebastia Sallent, Adaptive shared-state sampling, Proceedings of the 8th ACM SIGCOMM conference on Internet measurement, October 20-22, 2008, Vouliagmeni, Greece
	Naixue Xiong , Laurence T. Yang , Yingshu Li, ODMCA: An adaptive data mining control algorithm in multicarrier networks, Computer Communications, v.32 n.3, p.560-567, February, 2009
	Graham Cormode , Flip Korn , S. Muthukrishnan , Divesh Srivastava, Finding hierarchical heavy hitters in streaming data, ACM Transactions on Knowledge Discovery from Data (TKDD), v.1 n.4, p.1-48, January 2008
	Owen Kaser , Daniel Lemire, Removing manually generated boilerplate from electronic texts: experiments with project Gutenberg e-books, Proceedings of the 2007 conference of the center for advanced studies on Collaborative research, October 22-25, 2007, Richmond Hill, Ontario, Canada
	Graham Cormode , Marios Hadjieleftheriou, Finding frequent items in data streams, Proceedings of the VLDB Endowment, v.1 n.2, August 2008
	Claudio Silvestri , Salvatore Orlando, Approximate mining of frequent patterns on streams, Intelligent Data Analysis, v.11 n.1, p.49-73, January 2007
	Toon Calders , Nele Dexters , Bart Goethals, Mining frequent items in a stream using flexible windows, Intelligent Data Analysis, v.12 n.3, p.293-304, August 2008
	Radu Berinde , Graham Cormode , Piotr Indyk , Martin J. Strauss, Space-optimal heavy hitters with strong error bounds, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
	Ahmed Metwally , Fatih Emekçi , Divyakant Agrawal , Amr El Abbadi, SLEUTH: Single-pubLisher attack dEtection Using correlaTion Hunting, Proceedings of the VLDB Endowment, v.1 n.2, August 2008
	Carson Kai-Sang Leung , Dale A. Brajczuk , Jialiang Yu, Efficient algorithms for stream mining of constrained frequent patterns in a limited memory environment, Proceedings of the 2008 international symposium on Database engineering & applications, September 10-12, 2008, Coimbra, Portugal
	Jürgen Krämer , Bernhard Seeger, Semantics and implementation of continuous sliding window queries over data streams, ACM Transactions on Database Systems (TODS), v.34 n.1, p.1-49, April 2009
	Chaitanya Mishra , Nick Koudas, The design of a query monitoring system, ACM Transactions on Database Systems (TODS), v.34 n.1, p.1-51, April 2009
	Nishad Manerikar , Themis Palpanas, Frequent items in streaming data: An experimental evaluation of the state-of-the-art, Data & Knowledge Engineering, v.68 n.4, p.415-430, April, 2009
	Xiaoyu Wang , Hongyan Liu , Daoxin Er, HIDS: a multifunctional generator of hierarchical data streams, ACM SIGMIS Database, v.40 n.2, May 2009
	Xuejun Liu , Jihong Guan , Ping Hu, Mining frequent closed itemsets from a landmark window over online data streams, Computers & Mathematics with Applications, v.57 n.6, p.927-936, March, 2009
	En Tzu Wang , Arbee L. Chen, A novel hash-based approach for mining frequent itemsets over data streams requiring less memory space, Data Mining and Knowledge Discovery, v.19 n.1, p.132-172, August 2009
	Moonjung Cho , Jian Pei , Ke Wang, Answering ad hoc aggregate queries from data streams using prefix aggregate trees, Knowledge and Information Systems, v.12 n.3, p.301-329, August 2007
	Ke Yi , Qin Zhang, Optimal tracking of distributed heavy hitters and quantiles, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
	Carlos Rojas , Olfa Nasraoui, Online Evaluation of Patterns from Evolving Web Data Streams, Proceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, p.315-318, September 15-18, 2009