Approximate counting: a detailed analysis
From MaRDI portal
Publication:1057061
DOI10.1007/BF01934993zbMath0562.68027OpenAlexW2166332856WikidataQ57482531 ScholiaQ57482531MaRDI QIDQ1057061
Publication date: 1985
Published in: BIT (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01934993
Mellin transformanalysis of algorithmsbirth processcombinatorial analysisprobabilistic algorithmapproximate countingdirect samplingestimation methods
Analysis of algorithms and problem complexity (68Q25) Theory of operating systems (68N25) Algorithms in computer science (68W99)
Related Items (37)
Approximate counting with \(m\) counters: a probabilistic analysis ⋮ On Space and Time Complexity of Loosely-Stabilizing Leader Election ⋮ Rounding of continuous random variables and oscillatory asymptotics ⋮ \(q\)-distributions and Markov processes ⋮ An improved algorithm for transitive closure on acyclic digraphs ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Philippe Flajolet's early work in combinatorics ⋮ Ascending runs of sequences of geometrically distributed random variables: A probabilistic analysis ⋮ Randomized counter-based algorithms for frequency estimation over data streams in \(O(\log \log N)\) space ⋮ Consecutive records in geometrically distributed words ⋮ Unnamed Item ⋮ Exact and asymptotic distributions in digital and binary search trees ⋮ Approximate counting with \(m\) counters: A detailed analysis ⋮ The \(m\)-version of binary search trees: an average case analysis ⋮ An analytic approach to the asymptotic variance of trie statistics and related structures ⋮ Non-central generalized \(q\)-factorial coefficients and \(q\)-Stirling numbers ⋮ Advancing in the presence of a demon ⋮ A flexible way of counting large numbers approximately in small registers ⋮ Renewals for exponentially increasing lifetimes, with an application to digital search trees ⋮ Mellin transforms and asymptotics: Harmonic sums ⋮ Hypothetical analyses: Approximate counting in the style of Knuth, path length in the style of Flajolet ⋮ Generalized approximate counting revisited ⋮ Learned sketches for frequency estimation ⋮ Discrete \(q\)-distributions on Bernoulli trials with a geometrically varying success probability ⋮ Distinctness of compositions of an integer: A probabilistic analysis ⋮ Applying approximate counting for computing the frequency moments of long data streams ⋮ Approximate counting : an alternative approach ⋮ Counting to Ten with Two Fingers: Compressed Counting with Spiking Neurons. ⋮ The Big Match in Small Space ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Moments of a class of discrete \(q\)-distributions ⋮ The space complexity of approximating the frequency moments ⋮ Monotone runs of uniformly distributed integer random variables: A probabilistic analysis ⋮ Probabilistic counting algorithms for data base applications ⋮ Runs of geometrically distributed random variables: A probabilistic analysis
Cites Work
This page was built for publication: Approximate counting: a detailed analysis
