Python implementation of the dgim algorithm: Compact datastructure to estimate the number of "True" in the last N elements of a boolean stream.
Python implementation of the DGIM algorithm: a compact datastructure to estimate the number of True statements in the last N elements of a boolean stream.
When processing large streams of data such as clicks streams, server logs, financial streams. It is often necessary to maintain statistics about the N latest elements. If N is big or if you have many streams to process, it is not possible to store the N latest elements.
In such situations, if the processed stream is made of boolean, the DGIM algorithm can help you estimate the number of True statements in the last elements.
For instance, if the stream is made of server logs, DGIM algorithm can estimate the proportion of visits that come from search engines. (as opposed to direct access, or access through paid search)
At the command line:
$ pip install dgim
from dgim import Dgim dgim = Dgim(N=32, error_rate=0.1) for i in range(100): dgim.update(True) dgim_result = dgim.get_count() # 30 (exact result is 32)
The project is licensed under the BSD license.