Open AccessApproximate counting: A detailed analysis
Author(s) -
Philippe Flajolet
Publication year - 1985
Publication title -
bit numerical mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.904
H-Index - 59
eISSN - 1572-9125
pISSN - 0006-3835
DOI - 10.1007/bf01934993
Subject(s) - algorithm , convergence (economics) , mathematics , counting problem , computer science , economics , economic growth
Approximate counting is an algorithm proposed by R. Morris which makes it possible to keep approximate counts of large numbers in small counters. The algorithm is useful for gathering statistics of a large number of events as well as for applications related to data compression (Todd et al.). We provide here a complete analysis of approximate counting which establishes good convergence properties of the algorithm and allows to quantify precisely complexity-accuracy tradeoffs.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom