Probabilistic counting algorithms for data base applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Probabilistic counting algorithms for data base applications

Source

Journal of Computer and System Sciences archive
Volume 31 , Issue 2 (September 1985) table of contents

Pages: 182 - 209

Year of Publication: 1985

ISSN:0022-0000

Authors

Philippe Flajolet	INRIA, Rocquencourt, France
G. Nigel Martin	IBM Development Lab., Hursley Park, UK

Publisher

Academic Press, Inc. Orlando, FL, USA

Bibliometrics

Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 112

Additional Information:

cited by index terms review collaborative colleagues

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

DOI Bookmark:	10.1016/0022-0000(85)90041-8

CITED BY 112

	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	Navin Kabra , David J. DeWitt, Efficient mid-query re-optimization of sub-optimal query execution plans, ACM SIGMOD Record, v.27 n.2, p.106-117, June 1998
	Adam L. Buchsbaum , Raffaele Giancarlo , Jeffery R. Westbrook, On finding common neighborhoods in massive graphs, Theoretical Computer Science, v.299 n.1-3, p.707-718, 18 April 2003
	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
	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
	Ziv Bar-Yosseff , Ravi Kumar , D. Sivakumar, Reductions in streaming algorithms, with an application to counting triangles in graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.623-632, January 06-08, 2002, San Francisco, California
	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
	Frank Dehne , Todd Eavis , Susanne Hambrusch , Andrew Rau-Chaplin, Parallelizing the Data Cube, Distributed and Parallel Databases, v.11 n.2, p.181-201, March 2002
	Isaac Saias, Proving probabilistic correctness statements: the case of Rabin's algorithm for mutual exclusion, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.263-274, August 10-12, 1992, Vancouver, British Columbia, Canada
	M. Abdelguerfi , A. K. Sood, Computational Complexity of Sorting and Joining Relations with Duplicates, IEEE Transactions on Knowledge and Data Engineering, v.3 n.4, p.496-503, December 1991
	Christopher R. Palmer , Phillip B. Gibbons , Christos Faloutsos, ANF: a fast and scalable tool for data mining in massive graphs, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
	Thomas P. Nadeau , Toby J. Teorey, A Pareto model for OLAP view size estimation, Proceedings of the 2001 conference of the Centre for Advanced Studies on Collaborative research, p.13, November 05-07, 2001, Toronto, Ontario, Canada
	Yannis Kotidis, Aggregate view management in data warehouses, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Kanda Runapongsa , Thomas P. Nadeau , Toby J. Teorey, Storage estimation for multidimensional aggregates in OLAP, Proceedings of the 1999 conference of the Centre for Advanced Studies on Collaborative research, p.10, November 08-11, 1999, Mississauga, Ontario, Canada
	Phillip B. Gibbons , Srikanta Tirthapura, Distributed streams algorithms for sliding windows, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	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
	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
	Ying Chen , Frank Dehne , Todd Eavis , Andrew Rau-Chaplin, Parallel ROLAP Data Cube Construction on Shared-Nothing Multiprocessors, Distributed and Parallel Databases, v.15 n.3, p.219-236, May 2004
	Robert Schweller , Ashish Gupta , Elliot Parsons , Yan Chen, Reversible sketches for efficient and accurate change detection over network data streams, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy
	Fang Hao , Murali Kodialam , T. V. Lakshman, ACCEL-RATE: a faster mechanism for memory efficient per-flow traffic estimation, ACM SIGMETRICS Performance Evaluation Review, v.32 n.1, June 2004
	Suman Nath , Phillip B. Gibbons , Srinivasan Seshan , Zachary R. Anderson, Synopsis diffusion for robust aggregation in sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA
	Amit Manjhi , Suman Nath , Phillip B. Gibbons, Tributaries and deltas: efficient and robust aggregation in sensor network streams, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Cristian Estan , George Varghese , Mike Fisk, Bitmap algorithms for counting active flows on high speed links, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA
	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
	Paolo Boldi , Sebastiano Vigna, Mutable strings in Java: design, implementation and lightweight text-search algorithms, Science of Computer Programming, v.54 n.1, p.3-23, January 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
	Ken Keys , David Moore , Cristian Estan, A robust system for accurate real-time summaries of internet traffic, ACM SIGMETRICS Performance Evaluation Review, v.33 n.1, June 2005
	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
	Yufei Tao , Dimitris Papadias, Historical spatio-temporal aggregation, ACM Transactions on Information Systems (TOIS), v.23 n.1, p.61-102, January 2005
	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
	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
	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
	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
	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
	S. Keshav, Efficient and decentralized computation of approximate global state, ACM SIGCOMM Computer Communication Review, v.36 n.1, January 2006
	Peter J. Grabner , Arnold Knopfmacher , Helmut Prodinger, Combinatorics of geometrically distributed random variables: run statistics, Theoretical Computer Science, v.297 n.1-3, p.261-270, 17 March 2003
	Don Coppersmith , Ravi Kumar, An improved data stream algorithm for frequency moments, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Frank Dehne , Todd Eavis , Andrew Rau-Chaplin, The cgmCUBE project: Optimizing parallel data cube generation for ROLAP, Distributed and Parallel Databases, v.19 n.1, p.29-62, January 2006
	Alexandros G. Dimakis , Anand D. Sarwate , Martin J. Wainwright, Geographic gossip: efficient aggregation for sensor networks, Proceedings of the fifth international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA
	Sudipto Guha , Andrew McGregor, Approximate quantiles and the order of the stream, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	Damon Mosk-Aoyama , Devavrat Shah, Computing separable functions via gossip, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	Aiyou Chen , Li Li , Jin Cao, Estimating cardinality distributions in network traffic: extended abstract, ACM SIGMETRICS Performance Evaluation Review, v.36 n.1, June 2008
	Christian Lochert , Björn Scheuermann , Martin Mauve, Probabilistic aggregation for data dissemination in VANETs, Proceedings of the fourth ACM international workshop on Vehicular ad hoc networks, September 10-10, 2007, Montreal, Quebec, Canada
	Richard A. Wasniowski, Data fusion support for interfacing sensor networks to grid computing, Proceedings of the 9th WSEAS International Conference on Computers, p.1-4, July 14-16, 2005, Athens, Greece
	Nabeel Ahmed , David Hadaller , Srinivasan Keshav, GUESS: gossiping updates for efficient spectrum sensing, Proceedings of the 1st international workshop on Decentralized resource sharing in mobile computing and networking, July 25-25, 2006, Los Angeles, California
	Sankardas Roy , Sanjeev Setia , Sushil Jajodia, Attack-resilient hierarchical data aggregation in sensor networks, Proceedings of the fourth ACM workshop on Security of ad hoc and sensor networks, October 30-30, 2006, Alexandria, Virginia, USA
	Cristian Estan , George Varghese , Michael Fisk, Bitmap algorithms for counting active flows on high-speed links, IEEE/ACM Transactions on Networking (TON), v.14 n.5, p.925-937, October 2006
	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
	Xuemin Lin, Continuously maintaining order statistics over data streams: extended abstract, Proceedings of the eighteenth conference on Australasian database, p.7-10, January 30-February 02, 2007, Ballarat, Victoria, Australia
	Margaret Archibald , Arnold Knopfmacher , Helmut Prodinger, The number of distinct values in a geometrically distributed sample, European Journal of Combinatorics, v.27 n.7, p.1059-1081, October 2006
	Josiane Xavier Parreira , Debora Donato , Sebastian Michel , Gerhard Weikum, Efficient and decentralized PageRank approximation in a peer-to-peer web search network, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	David Pritchard , Santosh Vempala, Symmetric network computation, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Edith Cohen , Haim Kaplan, Spatially-decaying aggregation over a network, Journal of Computer and System Sciences, v.73 n.3, p.265-288, May, 2007
	Josiane Xavier Parreira , Sebastian Michel , Gerhard Weikum, p2pDating: Real life inspired semantic overlay networks for Web search, Information Processing and Management: an International Journal, v.43 n.3, p.643-664, May, 2007
	Sebastian Michel , Matthias Bender , Nikos Ntarmos , Peter Triantafillou , Gerhard Weikum , Christian Zimmer, Discovering and exploiting keyword and attribute-value co-occurrences to improve P2P routing indices, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
	Andrej Cvetkovski, An algorithm for approximate counting using limited memory resources, ACM SIGMETRICS Performance Evaluation Review, v.35 n.1, June 2007
	Edith Cohen , Haim Kaplan, Bottom-k sketches: better and more efficient estimation of aggregates, 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
	Markus G. Kuhn, Probabilistic counting of large digital signature collections, Proceedings of the 9th conference on USENIX Security Symposium, p.6-6, August 14-17, 2000, Denver, Colorado
	Sumeet Singh , Cristian Estan , George Varghese , Stefan Savage, Automated worm fingerprinting, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.4-4, December 06-08, 2004, San Francisco, CA
	Kevin Beyer , Peter J. Haas , Berthold Reinwald , Yannis Sismanis , Rainer Gemulla, On synopses for distinct-value estimation under multiset operations, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China
	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
	Graham Cormode , Mayur Datar , Piotr Indyk , S. Muthukrishnan, Comparing data streams using Hamming norms (how to zero in), Proceedings of the 28th international conference on Very Large Data Bases, p.335-345, August 20-23, 2002, Hong Kong, China
	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
	T. S. Jayram , Andrew McGregor , S. Muthukrishnan , Erik Vee, Estimating statistical aggregates on probabilistic data streams, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
	Amit Chakrabarti , Graham Cormode , Andrew McGregor, Robust lower bounds for communication and stream computation, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	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
	Abhinav Kamra , Vishal Misra , Dan Rubenstein, CountTorrent: ubiquitous access to query aggregates in dynamic and mobile sensor networks, Proceedings of the 5th international conference on Embedded networked sensor systems, November 06-09, 2007, Sydney, Australia
	Robert Schweller , Zhichun Li , Yan Chen , Yan Gao , Ashish Gupta , Yin Zhang , Peter A. Dinda , Ming-Yang Kao , Gokhan Memik, Reversible sketches: enabling monitoring and analysis over high-speed data streams, IEEE/ACM Transactions on Networking (TON), v.15 n.5, p.1059-1072, October 2007
	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
	Yossi Matias , Jeffrey Scott Vitter , Min Wang, Dynamic Maintenance of Wavelet-Based Histograms, Proceedings of the 26th International Conference on Very Large Data Bases, p.101-110, September 10-14, 2000
	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
	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
	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
	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
	Amit Shukla , Prasad Deshpande , Jeffrey F. Naughton , Karthikeyan Ramasamy, Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies, Proceedings of the 22th International Conference on Very Large Data Bases, p.522-531, September 03-06, 1996
	Avinash Sridharan , Tao Ye, Tracking port scanners on the IP backbone, Proceedings of the 2007 workshop on Large scale attack defense, August 27-27, 2007, Kyoto, Japan
	Sunita Sarawagi, iDiff: Informative Summarization of Differences in Multidimensional Aggregates, Data Mining and Knowledge Discovery, v.5 n.4, p.255-276, October 2001
	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
	Leiwen Deng , Yan Gao , Yan Chen , Aleksandar Kuzmanovic, Pollution attacks and defenses for Internet caching systems, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.52 n.5, p.935-956, April, 2008
	Sunil Chakkappen , Thierry Cruanes , Benoit Dageville , Linan Jiang , Uri Shaft , Hong Su , Mohamed Zait, Efficient and scalable statistics gathering for large databases in Oracle 11g, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
	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
	Man Lung Yiu , Nikos Mamoulis , Vagelis Hristidis, Extracting k most important groups from data efficiently, Data & Knowledge Engineering, v.66 n.2, p.289-310, August, 2008
	Christian Zimmer , Christos Tryfonopoulos , Gerhard Weikum, Exploiting correlated keywords to improve approximate information filtering, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore
	Joseph M. Hellerstein , Michael Stonebraker , James Hamilton, Architecture of a Database System, Foundations and Trends in Databases, v.1 n.2, p.141-259, February 2007
	Marios Hadjieleftheriou , Xiaohui Yu , Nick Koudas , Divesh Srivastava, Hashed samples: selectivity estimators for set similarity selection queries, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	James Aspnes , Keren Censor, Approximate shared-memory counting despite a strong adversary, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.441-450, January 04-06, 2009, New York, New York
	Hanhua Chen , Hai Jin , Jiliang Wang , Lei Chen , Yunhao Liu , Lionel M. Ni, Efficient multi-keyword search over p2p web, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China
	Haifeng Yu, DoS-resilient secure aggregation queries in sensor networks, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Edith Cohen , Haim Kaplan, Summarizing data using bottom-k sketches, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Laukik Chitnis , Alin Dobra , Sanjay Ranka, Aggregation methods for large-scale sensor networks, ACM Transactions on Sensor Networks (TOSN), v.4 n.2, p.1-36, March 2008
	Luca Becchetti , Carlos Castillo , Debora Donato , Ricardo Baeza-YATES , Stefano Leonardi, Link analysis for Web spam detection, ACM Transactions on the Web (TWEB), v.2 n.1, p.1-42, February 2008
	Hisashi Kurasawa , Hiromi Wakaki , Atsuhiro Takasu , Jun Adachi, Data allocation scheme based on term weight for P2P information retrieval, Proceedings of the 9th annual ACM international workshop on Web information and data management, November 09-09, 2007, Lisbon, Portugal
	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
	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
	Suman Nath , Phillip B. Gibbons , Srinivasan Seshan , Zachary Anderson, Synopsis diffusion for robust aggregation in sensor networks, ACM Transactions on Sensor Networks (TOSN), v.4 n.2, p.1-40, March 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
	T. S. Jayram , Andrew McGregor , S. Muthukrishnan , Erik Vee, Estimating statistical aggregates on probabilistic data streams, ACM Transactions on Database Systems (TODS), v.33 n.4, p.1-30, November 2008
	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
	He Sun , Chung Keung Poon, Two improved range-efficient algorithms for F0 estimation, Theoretical Computer Science, v.410 n.11, p.1073-1080, March, 2009
	M. A. Iwen , C. V. Spencer, A note on compressed sensing and the complexity of matrix multiplication, Information Processing Letters, v.109 n.10, p.468-471, April, 2009
	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
	David P. Woodruff, The average-case complexity of counting distinct elements, Proceedings of the 12th International Conference on Database Theory, March 23-25, 2009, St. Petersburg, Russia
	Suman Nath , Haifeng Yu , Haowen Chan, Secure outsourced aggregation via one-way chains, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA
	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
	Devavrat Shah, Gossip Algorithms, Foundations and Trends® in Networking, v.3 n.1, p.1-125, January 2009
	Haifeng Yu, Secure and highly-available aggregation queries in large-scale sensor networks via set sampling, Proceedings of the 2009 International Conference on Information Processing in Sensor Networks, p.1-12, April 13-16, 2009
	Jian Wang , Brian D. Davison, Counting ancestors to estimate authority, Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval, July 19-23, 2009, Boston, MA, USA
	Yubing Wang , Mark Claypool , Robert Kinicki, Modeling RPS and evaluating video repair with VQM, IEEE Transactions on Multimedia, v.11 n.1, p.128-137, January 2009

INDEX TERMS

Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.1 Numerical Algorithms and Problems
Subjects: Number-theoretic computations (e.g., factoring, primality testing)

G. Mathematics of Computing
G.3 PROBABILITY AND STATISTICS
Subjects: Probabilistic algorithms (including Monte Carlo)

H. Information Systems
H.2 DATABASE MANAGEMENT
H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Algorithms, Measurement

REVIEW

"Theodore David Brown : Reviewer"

The algorithm presented here bounds the number of distinct elements (n) in a large collection of data records. The essence of the algorithm is to “or” to a bit vector the least significant one bit of a hashed version of ea more...

Collaborative Colleagues:

Philippe Flajolet: colleagues

G. Nigel Martin: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player