| 摘要 |
Methods, systems and apparatus, including computer programs encoded on computer storage media for approximating item counts. One of the methods includes maintaining a collection of counters for a class of items, processing each item in an item stream as a current item, including determining whether or not the collection includes an item counter for the current item, and if the collection includes an item counter for the current item, updating each count level in the item counter for the current item. |
| 主权项 |
1. A computer-implemented method comprising:
maintaining a collection of counters for a class of items, wherein the collection includes a respective item counter for each distinct item in the class of items, wherein each item counter has one or more count levels, wherein each count level has a respective time-ordered list of one or more count blocks, and wherein each count block has a respective offset and a respective timestamp; processing each item in an item stream as a current item, including:
determining whether or not the collection includes an item counter for the current item; andif the collection includes an item counter for the current item, updating each count level in the item counter for the current item, including determining whether a timestamp of the current item is more recent than a timestamp of a most recent count block in the time-ordered list of the count level,
(i) and if so, updating the count level by adding, to the time-ordered list of the count level, a count block having the timestamp of the current item,(ii) and otherwise, identifying, in the time-ordered list of the count level, a count block having a timestamp that is closest in time to the timestamp of the current item, and updating the respective count level by incrementing an offset of the identified count block.
|
