How to count quickly and accurately: A unified analysis of probabilistic counting and other related problems

DOI10.1007/3-540-55719-9_75zbMath1425.68474OpenAlexW2164983825MaRDI QIDQ5204318

Peter Kirschenhofer, Wojciech Szpankowski, Prodinger, Helmut

Publication date: 4 December 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://docs.lib.purdue.edu/cstech/918

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorics in computer science (68R05)

Related Items (1)

Combinatorics of geometrically distributed random variables: Left-to-right maxima

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• How to select a loser
• Probabilistic counting algorithms for data base applications
• Yet another application of a binomial recurrence. Order statistics
• How many random questions are necessary to identify \(n\) distinct objects?
• Approximate counting : an alternative approach
• Patricia tries again revisited
• Singularity Analysis of Generating Functions
• Estimating the multiplicities of conflicts to speed their resolution in multiple access channels
• Solution of a Linear Recurrence Equation Arising in the Analysis of Some Algorithms
• Generalized Digital Trees and Their Difference—Differential Equations
• Counting large numbers of events in small registers
• Limiting Distribution for the Depth in PATRICIA Tries
• Ultimate Characterizations of the Burst Response of an Interval Searching Algorithm: A Study of a Functional Equation
• The average CRI-length of a tree collision resolution algorithm in presence of multiplicity-dependent capture effects

This page was built for publication: How to count quickly and accurately: A unified analysis of probabilistic counting and other related problems