The space complexity of approximating the frequency moments

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The space complexity of approximating the frequency moments

Full text

Pdf (1.07 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-eighth annual ACM symposium on Theory of computing table of contents

Philadelphia, Pennsylvania, United States

Pages: 20 - 29

Year of Publication: 1996

ISBN:0-89791-785-5

Authors

Noga Alon	AT&T Bell Labs, Murray Hill, NJ and Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel
Yossi Matias	AT&T Bell Labs, Murray Hill, NJ
Mario Szegedy	AT&T Bell Labs, Murray Hill, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 32, Downloads (12 Months): 315, Citation Count: 124

Additional Information:

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/237814.237823 What is a DOI?

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 , László Babai , Alon Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, v.7 n.4, p.567-583, Dec. 1986 [doi>10.1016/0196-6774(86)90019-2]
	2	N. Alon, P. Gibbons, Y. Matias and M. Szegedy, Dynarnic probabilistic maintenance of self-join sizes in limited storage, manuscript, Feb. 1996.
	3	N. Alon and J. H. Spencer, The Probabilistic Method, John Wiley and Sons Inc., New York, 1992.
	4	L. Bahai, P. Frankl and J. Simon, Complexity classes in communicatwn complexity theory, Proc. of the 27~h IEEE FOCS, 1986, 337-347.
	5	Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
	6	David J. DeWitt , Jeffrey F. Naughton , Donovan A. Schneider , S. Seshadri, Practical Skew Handling in Parallel Joins, Proceedings of the 18th International Conference on Very Large Data Bases, p.27-40, August 23-27, 1992
	7	Philippe Flajolet, Approximate counting: a detailed analysis, BIT, v.25 n.1, p.113-134, 1985 [doi>10.1007/BF01934993]
	8	P. Flajolet and G. N. Martin, Probabihstic counting, FOCS 1983, 76-82.
	9	P. Gibbons, Y. Matias and A. Witkowski, Practical maintenance algorithms for high. biased histograms using probabilistic filtering, Technical Report, AT&T Bell Laboratories, Murray Hill, NJ, Dec. 1995.
	10	A. Gupta and I.S. Mumick, Maintenance of Materialized View: Problems, Techniques, and Applications, IEEE Data Engineering Bulletin, Special Issue on Materialized Views and Data Warehousing, 18(2), (1995).
	11	I. J. Good, Surprise indexes and P.values, j. Statistical Computation and Simulation 32 (1989), 90-92.
	12	M. Hofri and N. Kechris, Probabilistic counting of a large number of events, manuscript, 1995.
	13	Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Lynne Stokes, Sampling-Based Estimation of the Number of Distinct Values of an Attribute, Proceedings of the 21th International Conference on Very Large Data Bases, p.311-322, September 11-15, 1995
	14	Yannis E. Ioannidis , Viswanath Poosala, Balancing histogram optimality and practicality for query result size estimation, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.233-244, May 22-25, 1995, San Jose, California, United States
	15	B. Kalyanasundaram and G. Schnitger, The probabilis. tic communication complexity of set intersection, 2'~a Structure in Complexity Theory Conf. (1987), 41-49.
	16	Yibei Ling , Wei Sun, A supplement to sampling-based methods for query size estimation in a database system, ACM SIGMOD Record, v.21 n.4, p.12-15, Dec. 1992 [doi>10.1145/141818.141820]
	17	Robert Morris, Counting large numbers of events in small registers, Communications of the ACM, v.21 n.10, p.840-842, Oct. 1978 [doi>10.1145/359619.359627]
	18	A. A. Razborov, On the distributional complexity of disjointness, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.249-253, July 1990, Warwick University, England
	19	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]
	20	Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]
	21	A. C. Yao, Lower bounds by probabilistic arguments, Proc of the 24th IEEE FOCS, 1983, 420-428.

CITED BY 124

	Noga Alon , Phillip B. Gibbons , Yossi Matias , Mario Szegedy, Tracking join and self-join sizes in limited storage, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.10-20, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	Alin Dobra , Minos Garofalakis , Johannes Gehrke , Rajeev Rastogi, Processing complex aggregate queries over data streams, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
	Michael Saks , Xiaodong Sun, Space lower bounds for distance approximation in the data stream model, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Phillip B. Gibbons , Srikanta Tirthapura, Estimating simple functions on the union of data streams, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.281-291, July 2001, Crete Island, Greece
	Moses Charikar , Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, Towards estimation error guarantees for distinct values, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.268-279, May 15-18, 2000, Dallas, Texas, United States
	Phillip B. Gibbons , Yossi Matias, New sampling-based summary statistics for improving approximate query answers, ACM SIGMOD Record, v.27 n.2, p.331-342, June 1998
	Petros Drineas , Ravi Kannan, Pass efficient algorithms for approximating large matrices, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Minos Garofalakis , Amit Kumar, Correlating XML data streams using tree-edit distance embeddings, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.143-154, June 09-11, 2003, San Diego, California
	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
	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
	Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala , Sridhar Ramaswamy, Join synopses for approximate query answering, ACM SIGMOD Record, v.28 n.2, p.275-286, June 1999
	Phillip B. Gibbons , Yossi Matias, Synopsis data structures for massive data sets, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.909-910, January 17-19, 1999, Baltimore, Maryland, United States
	Richard M. Karp , Scott Shenker , Christos H. Papadimitriou, A simple algorithm for finding frequent elements in streams and bags, ACM Transactions on Database Systems (TODS), v.28 n.1, p.51-55, March 2003
	Lukasz Golab , M. Tamer Özsu, Issues in data stream management, ACM SIGMOD Record, v.32 n.2, p.5-14, June 2003
	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
	Lakshminath Bhuvanagiri , Sumit Ganguly , Deepanjan Kesh , Chandan Saha, Simpler algorithm for estimating frequency moments of data streams, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.708-713, January 22-26, 2006, Miami, Florida
	Antonios Deligiannakis , Nick Roussopoulos, Extended wavelets for multiple measures, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
	Wei Wang , Haifeng Jiang , Hongjun Lu , Jeffrey Xu Yu, Containment join size estimation: models and methods, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
	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
	Mayur Datar , Aristides Gionis , Piotr Indyk , Rajeev Motwani, Maintaining stream statistics over sliding windows: (extended abstract), Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.635-644, January 06-08, 2002, San Francisco, California
	Piotr Indyk, Algorithms for dynamic geometric problems over data streams, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Sumit Ganguly , Minos Garofalakis , Rajeev Rastogi, Processing set expressions over continuous update streams, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
	Sudipto Guha , Adam Meyerson , Nina Mishra , Rajeev Motwani , Liadan O'Callaghan, Clustering Data Streams: Theory and Practice, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.515-528, March 2003
	Sudipto Guha , D. Gunopulos , Nick Koudas, Correlating synchronous and asynchronous data streams, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
	Raghav Kaushik , Jeffrey F. Naughton , Raghu Ramakrishnan , Venkatesan T. Chakravarthy, Synopses for query optimization: A space-complexity perspective, ACM Transactions on Database Systems (TODS), v.30 n.4, p.1102-1127, December 2005
	Abhinandan Das , Johannes Gehrke , Mirek Riedewald, Approximation techniques for spatial data, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	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
	Mayank Bawa , Aristides Gionis , Hector Garcia-Molina , Rajeev Motwani, The price of validity in dynamic networks, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	David Woodruff, Optimal space lower bounds for all frequency moments, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Graham Cormode , Minos Garofalakis , S. Muthukrishnan , Rajeev Rastogi, Holistic aggregates in a networked world: distributed tracking of approximate quantiles, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	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
	Alin Dobra, Histograms revisited: when are histograms the best approximation method for aggregates over joins?, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
	Kirill Levchenko , Ramamohan Paturi , George Varghese, On the difficulty of scalably detecting network attacks, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA
	Shivnath Babu , Jennifer Widom, Continuous queries over data streams, ACM SIGMOD Record, v.30 n.3, September 2001
	Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, One-Pass Wavelet Decompositions of Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.541-554, March 2003
	Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, Domain-Driven Data Synopses for Dynamic Quantiles, IEEE Transactions on Knowledge and Data Engineering, v.17 n.7, p.927-938, July 2005
	Piotr Indyk , David Woodruff, Optimal approximations of the frequency moments of data streams, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Angeline Wong , Leejay Wu , Phillip B. Gibbons , Christos Faloutsos, Fast estimation of fractal dimension and correlation integral on stream data, Information Processing Letters, v.93 n.2, p.91-97, 31 January 2005
	Joseph M. Hellerstein , Wei Wang, Optimization of in-network data reduction, Proceeedings of the 1st international workshop on Data management for sensor networks: in conjunction with VLDB 2004, August 30-30, 2004, Toronto, Canada
	A. R. Calderbank , A. Gilbert , K. Levchenko , S. Muthukrishnan , M. Strauss, Improved range-summable random variable construction algorithms, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Minos Garofalakis , Amit Kumar, XML stream processing using tree-edit distance embeddings, ACM Transactions on Database Systems (TODS), v.30 n.1, p.279-332, 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
	Graham Cormode , S. Muthukrishnan, An improved data stream summary: the count-min sketch and its applications, Journal of Algorithms, v.55 n.1, p.58-75, April 2005
	Graham Cormode , Minos Garofalakis, Sketching streams through the net: distributed approximate query tracking, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Graham Cormode , S. Muthukrishnan , Irina Rozenbaum, Summarizing and mining inverse distributions on data streams via dynamic inverse sampling, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Graham Cormode , S. Muthukrishnan, Space efficient mining of multigraph streams, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
	Gereon Frahling , Christian Sohler, Coresets in dynamic geometric data streams, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Gereon Frahling , Piotr Indyk , Christian Sohler, Sampling in dynamic data streams and applications, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Sumit Ganguly , Minos Garofalakis , Amit Kumar , Rajeev Rastogi, Join-distinct aggregate estimation over update streams, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
	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
	Kevin L. Chang , Ravi Kannan, The space complexity of pass-efficient algorithms for clustering, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1157-1166, January 22-26, 2006, Miami, Florida
	Raghav Kaushik , Raghu Ramakrishnan , Venkatesan T. Chakaravarthy, Synopses for query optimization: a space-complexity perspective, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
	Bartosz Przydatek , Dawn Song , Adrian Perrig, SIA: secure information aggregation in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA
	Shahar Dobzinski , Michael Schapira, An improved approximation algorithm for combinatorial auctions with submodular bidders, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1064-1073, January 22-26, 2006, Miami, Florida
	Ping Li , Trevor J. Hastie , Kenneth W. Church, Very sparse random projections, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
	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
	Arvind Arasu , Brian Babcock , Shivnath Babu , Jon McAlister , Jennifer Widom, Characterizing memory requirements for queries over continuous data streams, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
	A. C. Gilbert , S. Guha , P. Indyk , S. Muthukrishnan , M. Strauss, Near-optimal sparse fourier representations via sampling, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Daniel Lemire , Owen Kaser, Hierarchical bin buffering: Online local moments for dynamic external memory arrays, ACM Transactions on Algorithms (TALG), v.4 n.1, p.1-31, March 2008
	Michael Stacey , Carolyn McGregor, Temporal abstraction in intelligent clinical data analysis: A survey, Arificial Intelligence in Medicine, v.39 n.1, p.1-24, January, 2007
	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
	Arvind Arasu , Venkatesh Ganti , Raghav Kaushik, Efficient exact set-similarity joins, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Florin Rusu , Alin Dobra, Fast range-summable random variables for efficient aggregate estimation, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
	Joshua Spiegel , Neoklis Polyzotis, Graph-based synopses for relational selectivity estimation, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
	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
	Liad Blumrosen , Shahar Dobzinski, Welfare maximization in congestion games, Proceedings of the 7th ACM conference on Electronic commerce, p.52-61, June 11-15, 2006, Ann Arbor, Michigan, USA
	Ashwin Lall , Vyas Sekar , Mitsunori Ogihara , Jun Xu , Hui Zhang, Data streaming algorithms for estimating entropy of network traffic, ACM SIGMETRICS Performance Evaluation Review, v.34 n.1, June 2006
	Florin Rusu , Alin Dobra, Pseudo-random number generation for sketch-based estimations, ACM Transactions on Database Systems (TODS), v.32 n.2, p.11-es, June 2007
	Andrej Cvetkovski, An algorithm for approximate counting using limited memory resources, ACM SIGMETRICS Performance Evaluation Review, v.35 n.1, June 2007
	Sumit Ganguly, Counting distinct items over update streams, Theoretical Computer Science, v.378 n.3, p.211-222, June, 2007
	Mayank Bawa , Aristides Gionis , Hector Garcia-Molina , Rajeev Motwani, The price of validity in dynamic networks, Journal of Computer and System Sciences, v.73 n.3, p.245-264, May, 2007
	Wei Wang , Minos Garofalakis , Kannan Ramchandran, Distributed sparse random projections for refinable approximation, Proceedings of the 6th international conference on Information processing in sensor networks, April 25-27, 2007, Cambridge, Massachusetts, USA
	George Varghese , J. Andrew Fingerhut , Flavio Bonomi, Detecting evasion attacks at high speeds without reassembly, ACM SIGCOMM Computer Communication Review, v.36 n.4, October 2006
	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
	Xiao-Bo Fan , Ting-Ting Xie , Cui-Ping Li , Hong Chen, MRST: an efficient monitoring technology of summarization on stream data, Journal of Computer Science and Technology, v.22 n.2, p.190-196, March 2007
	Jeffery Xu Yu , Zhihong Chong , Hongjun Lu , Aoying Zhou, False positive or false negative: mining frequent itemsets from high speed transactional data streams, Proceedings of the Thirtieth international conference on Very large data bases, p.204-215, August 31-September 03, 2004, Toronto, Canada
	Gurmeet Singh Manku , Rajeev Motwani, Approximate frequency counts over data streams, Proceedings of the 28th international conference on Very Large Data Bases, p.346-357, August 20-23, 2002, Hong Kong, China
	Izchak Sharfman , Assaf Schuster , Daniel Keren, Shape sensitive geometric monitoring, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada
	Florin Rusu , Alin Dobra, Statistical analysis of sketch estimators, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China
	Graham Cormode , Minos Garofalakis, Sketching probabilistic data streams, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China
	Izchak Sharfman , Assaf Schuster , Daniel Keren, A geometric approach to monitoring threshold functions over distributed data streams, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
	Y. Ogras , Hakan Ferhatosmanoglu, Online summarization of dynamic time series data, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.1, p.84-98, January 2006
	Soumen Chakrabarti , Byron Dom , Rakesh Agrawal , Prabhakar Raghavan, Scalable feature selection, classification and signature generation for organizing large text databases into hierarchical topic taxonomies, The VLDB Journal — The International Journal on Very Large Data Bases, v.7 n.3, p.163-178, August 1998
	Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin Strauss, Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries, Proceedings of the 27th International Conference on Very Large Data Bases, p.79-88, September 11-14, 2001
	Phillip B. Gibbons, Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports, Proceedings of the 27th International Conference on Very Large Data Bases, p.541-550, September 11-14, 2001
	Minos N. Garofalakis , Phillip B. Gibbon, Approximate Query Processing: Taming the TeraBytes, Proceedings of the 27th International Conference on Very Large Data Bases, p.725, September 11-14, 2001
	Christos Faloutsos , Yossi Matias , Abraham Silberschatz, Modeling Skewed Distribution Using Multifractals and the `80-20' Law, Proceedings of the 22th International Conference on Very Large Data Bases, p.307-317, September 03-06, 1996
	Ping Li , Kenneth W. Church, A Sketch Algorithm for Estimating Two-Way and Multi-Way Associations, Computational Linguistics, v.33 n.3, p.305-354, September 2007
	Sumit Ganguly , Minos Garofalakis , Rajeev Rastogi, Tracking set-expression cardinalities over continuous update streams, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.4, p.354-369, December 2004
	Gagan Aggarwal , Nir Ailon , Florin Constantin , Eyal Even-Dar , Jon Feldman , Gereon Frahling , Monika R. Henzinger , S. Muthukrishnan , Noam Nisan , Martin Pál , Mark Sandler , Anastasios Sidiropoulos, Theory research at Google, ACM SIGACT News, v.39 n.2, June 2008
	Alexandr Andoni , Piotr Indyk , Robert Krauthgamer, Overcoming the l₁ non-embeddability barrier: algorithms for product metrics, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.865-874, January 04-06, 2009, New York, New York
	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 , Minos Garofalakis, Approximate continuous querying over distributed streams, ACM Transactions on Database Systems (TODS), v.33 n.2, p.1-39, June 2008
	J. Aguilar-Saborit , P. Trancoso , V. Muntes-Mulero , J. L. Larriba-Pey, Dynamic adaptive data structures for monitoring data streams, Data & Knowledge Engineering, v.66 n.1, p.92-115, July, 2008
	Wei Dong , Moses Charikar , Kai Li, Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore
	Feng Yan , Wen-Chi Hou , Zhewei Jiang , Cheng Luo , Qiang Zhu, Selectivity estimation of range queries based on data density approximation via cosine series, Data & Knowledge Engineering, v.63 n.3, p.855-878, December, 2007
	Piotr Indyk, Explicit constructions for compressed sensing of sparse signals, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.30-33, January 20-22, 2008, San Francisco, California
	Izchak Sharfman , Assaf Schuster , Daniel Keren, A geometric approach to monitoring threshold functions over distributed data streams, ACM Transactions on Database Systems (TODS), v.32 n.4, p.23-es, November 2007
	Hai Wang , Kenneth C. Sevcik, Histograms based on the minimum description length principle, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.3, p.419-442, May 2008
	Xiaoming Sun , David P. Woodruff, The communication and streaming complexity of computing the longest common and increasing subsequences, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.336-345, January 07-09, 2007, New Orleans, Louisiana
	Ping Li, Very sparse stable random projections for dimension reduction in lα (0 <α ≤ 2) norm, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA
	Aiyou Chen , Jin Cao , Tian Bu, A simple and efficient estimation method for stream expression cardinalities, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Jon Feldman , S. Muthukrishnan , Anastasios Sidiropoulos , Cliff Stein , Zoya Svitkina, On distributing symmetric streaming computations, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.710-719, January 20-22, 2008, San Francisco, California
	Ahmed Metwally , Divyakant Agrawal , Amr El Abbadi, Why go logarithmic if we can go linear?: Towards effective distinct counting of search traffic, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
	Haowen Chan , Adrian Perrig , Bartosz Przydatek , Dawn Song, SIA: Secure information aggregation in sensor networks, Journal of Computer Security, v.15 n.1, p.69-102, January 2007
	Cheqing Jin , Ke Yi , Lei Chen , Jeffrey Xu Yu , Xuemin Lin, Sliding-window top-k queries on uncertain streams, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Fabian Kuhn , Thomas Locher , Stefan Schmid, Distributed computation of the mode, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Graham Cormode , Marios Hadjieleftheriou, Finding frequent items in data streams, Proceedings of the VLDB Endowment, v.1 n.2, August 2008
	Sharon Goldberg , David Xiao , Eran Tromer , Boaz Barak , Jennifer Rexford, Path-quality monitoring in the presence of adversaries, ACM SIGMETRICS Performance Evaluation Review, v.36 n.1, June 2008
	Valerie King , Cynthia Phillips , Jared Saia , Maxwell Young, Sleeping on the job: energy-efficient and robust broadcast for radio networks, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Florin Rusu , Alin Dobra, Sketches for size of join estimation, ACM Transactions on Database Systems (TODS), v.33 n.3, p.1-46, August 2008
	Cheng Luo , Zhewei Jiang , Wen-Chi Hou , Feng Yan , Qiang Zhu, A relational model for XML structural joins and their size estimations, Knowledge and Information Systems, v.16 n.1, p.97-127, July 2008
	Alin Dobra , Minos Garofalakis , Johannes Gehrke , Rajeev Rastogi, Multi-query optimization for sketch-based estimation, Information Systems, v.34 n.2, p.209-230, April, 2009
	N. Ntarmos , P. Triantafillou , G. Weikum, Distributed hash sketches: Scalable, efficient, and accurate cardinality estimation for distributed multisets, ACM Transactions on Computer Systems (TOCS), v.27 n.1, p.1-53, February 2009
	Ping Li, Compressed counting, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.412-421, January 04-06, 2009, New York, New York
	Vladimir Braverman , Rafail Ostrovsky , Carlo Zaniolo, Optimal sampling from sliding windows, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
	João Gama , Pedro Rodrigues , Jesú Aguilar-Ruiz, Preface: an overview on learning from data streams, New Generation Computing, v.25 n.1, p.1-4, January 2007
	Hillol Kargupta , Vasundhara Puttagunta , Martin Klein , Kakali Sarkar, On-board vehicle data stream monitoring using mine-fleet and fast resource constrained monitoring of correlation matrices, New Generation Computing, v.25 n.1, p.5-32, January 2007
	Joshua Spiegel , Neoklis Polyzotis, TuG synopses for approximate query answering, ACM Transactions on Database Systems (TODS), v.34 n.1, p.1-56, April 2009
	Jeffrey Considine , Marios Hadjieleftheriou , Feifei Li , John Byers , George Kollios, Robust approximate aggregation in sensor data management systems, ACM Transactions on Database Systems (TODS), v.34 n.1, p.1-35, April 2009
	Edward Bortnikov , Maxim Gurevich , Idit Keidar , Gabriel Kliot , Alexander Shraer, Brahms: Byzantine resilient random membership sampling, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.53 n.13, p.2340-2359, August, 2009
	Charalampos E. Tsourakakis , U. Kang , Gary L. Miller , Christos Faloutsos, DOULION: counting triangles in massive graphs with a coin, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, June 28-July 01, 2009, Paris, France
	Yutao Zhong , Xipeng Shen , Chen Ding, Program locality analysis using reuse distance, ACM Transactions on Programming Languages and Systems (TOPLAS), v.31 n.6, p.1-39, August 2009