Browse Prior Art Database

Method for Probabilistic Incrementation of Approximate Counters

IP.com Disclosure Number: IPCOM000075043D
Original Publication Date: 1971-Jul-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 2 page(s) / 19K

Publishing Venue

IBM

Related People

Davison, GA: AUTHOR

Abstract

This is a method to economize by replacing a normal counter having n bits, with an approximate counter having the same range and the ability to count or increment by one and yet requiring only log(2)(n+1) bits. A value k stored in the approximation counter represents any of the range of numbers 2(k-1) through 2/k/-1 that might have been stored in a normal counter. Incrementation is done on a probabilistic basis; at each count increment time a random number generator is used to generate a number between zero and 2/(k-1)/-1 and if the random number is zero, one is added to the value k in the approximate counter.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 82% of the total text.

Page 1 of 2

Method for Probabilistic Incrementation of Approximate Counters

This is a method to economize by replacing a normal counter having n bits, with an approximate counter having the same range and the ability to count or increment by one and yet requiring only log(2)(n+1) bits. A value k stored in the approximation counter represents any of the range of numbers 2(k-1) through 2/k/-1 that might have been stored in a normal counter. Incrementation is done on a probabilistic basis; at each count increment time a random number generator is used to generate a number between zero and 2/(k-1)/-1 and if the random number is zero, one is added to the value k in the approximate counter.

For example, a 3-bit approximate counter may count from 0 to 127 as shown below, while 7 bits would be needed for exact counting.

(Image Omitted)

To increment the approximation counter from, for example, k=4 to k=5, and remain true to the approximation built in, the addition should be performed at only one count increment time in eight since the approximate count k=4 represents a range of eight numbers. Adding one to k with probability P = 2/(1-k) at each count increment time accomplishes this on a probabilistic basis. (This introduces the possibility of probabilistic errors and thus, the counter is only approximate.) The actual decision at each count increment time of whether or not to add one to k is achieved by use of a random number, as mentioned above.

The approximate counter described onl...