4 ms·

I was interested in using HLL for a project where I had ~20 million objects and each had a "status" with about 6 possibilities. I wanted to get fast counts of h

I was interested in using HLL for a project where I had ~20 million objects and each had a "status" with about 6 possibilities. I wanted to get fast counts of how many objects were in each status. But their status can change over time, so I needed a way to also remove items from the count. HLL doesn't support this. Does anyone know of an algorithm that does? (Keeping a separate HLL for "removed" doesn't help because objects can revisit the same status they had before.)

vogtb 9y ago
A couple of days late, but you can solve this by recording changes rather than objects themselves. So you log the timestamp of the status changes with the "id" of element you're changing. Then you when an object goes from one status to another, you can record a concat of the id and old timestamp to the "remove" hyperloglog for the previous status, and then record the concat of the id and the new timestamp to the "add" hyperloglog for the current state. Say you object A at time=1 is being recorded as "At=1" for status R. If it moves to status Q at time=2, you record "At=1" to the hyperloglog for your status R "removes", and then "At=2" for the status R hyperloglog. This works with objects changing status NOT more than once for however you're measuring time. If you're using milliseconds and the status changes infrequently, you're probably good. The down side is this requires you to track changes rather than just iterate through your objects, so it might not be compatible with your architecture. You also would have to iterate through all objects to capture their initial status. It also is susceptible to errors increasing over time, as your "add" and "remove" hyperloglogs will record more and more elements (re: changes) over time.
seiflotfy 9y ago
https://github.com/seiflotfy/cuckoofilter https://github.com/seiflotfy/cuckoofilter but this will require you to know how many max unique values per status your will have.
teej 9y ago
I'm sure you thought of this, but what are the drawbacks to simply INCR/DECR some counters when an object changes state?
- pjungwir 9y ago
  Indeed after ruling out HLL I decided that was the way to go. :-) I guess an HLL is more appropriate when you can't so easily keep track of which items have already been added to each set. For example if you were counting unique visitors per day, you would have a lot of sets (one per day), so you wouldn't want to store n visitor IDs for every day. But when an item can only be in one set at a time (and the sets are finite) incr/decr is possible so you might as well go with it.
E6300 9y ago
Perhaps I'm misunderstanding the problem, but is maintaining six integers and updating their values as objects move from one status to another not a suitable solution?
contravariant 9y ago
HLL is for calculating the number of unique objects when there are possible duplicates. Unless you're doing something really weird you shouldn't have any problem going through all 20 million objects without encountering duplicates. You're probably better of just keeping a running total. You can either update this total online (keeping track of all state changes) or whenever you need to know (going through a mere 20 million items shouldn't take too long). If, for whatever reason, you really want to approximate it quickly, just pick a subset at random and calculate the percentages from there. Some basic Bayesian statistics can tell you the accuracy of this approximation.
zintinio5 9y ago
If what you want is an approximate answer, take a look at * Counting Bloom Filter https://en.wikipedia.org/wiki/Bloom_filter#Counting_filters https://en.wikipedia.org/wiki/Bloom_filter#Counting_filters * Count-Min Sketch https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch Here's a library: https://datasketches.github.io/ https://datasketches.github.io/ However, you can probably fit an exact answer into memory with just a simple hashtable if you've only got 20 million objects. A single byte could be used as the state marker. Either that, or just track 6 counts.

vogtb 9y ago

A couple of days late, but you can solve this by recording changes rather than objects themselves. So you log the timestamp of the status changes with the "id" of element you're changing. Then you when an object goes from one status to another, you can record a concat of the id and old timestamp to the "remove" hyperloglog for the previous status, and then record the concat of the id and the new timestamp to the "add" hyperloglog for the current state. Say you object A at time=1 is being recorded as "At=1" for status R. If it moves to status Q at time=2, you record "At=1" to the hyperloglog for your status R "removes", and then "At=2" for the status R hyperloglog. This works with objects changing status NOT more than once for however you're measuring time. If you're using milliseconds and the status changes infrequently, you're probably good. The down side is this requires you to track changes rather than just iterate through your objects, so it might not be compatible with your architecture. You also would have to iterate through all objects to capture their initial status. It also is susceptible to errors increasing over time, as your "add" and "remove" hyperloglogs will record more and more elements (re: changes) over time.

seiflotfy 9y ago

https://github.com/seiflotfy/cuckoofilter https://github.com/seiflotfy/cuckoofilter but this will require you to know how many max unique values per status your will have.

teej 9y ago

I'm sure you thought of this, but what are the drawbacks to simply INCR/DECR some counters when an object changes state?

pjungwir 9y ago
Indeed after ruling out HLL I decided that was the way to go. :-) I guess an HLL is more appropriate when you can't so easily keep track of which items have already been added to each set. For example if you were counting unique visitors per day, you would have a lot of sets (one per day), so you wouldn't want to store n visitor IDs for every day. But when an item can only be in one set at a time (and the sets are finite) incr/decr is possible so you might as well go with it.

E6300 9y ago

Perhaps I'm misunderstanding the problem, but is maintaining six integers and updating their values as objects move from one status to another not a suitable solution?

contravariant 9y ago

HLL is for calculating the number of unique objects when there are possible duplicates. Unless you're doing something really weird you shouldn't have any problem going through all 20 million objects without encountering duplicates. You're probably better of just keeping a running total. You can either update this total online (keeping track of all state changes) or whenever you need to know (going through a mere 20 million items shouldn't take too long). If, for whatever reason, you really want to approximate it quickly, just pick a subset at random and calculate the percentages from there. Some basic Bayesian statistics can tell you the accuracy of this approximation.

zintinio5 9y ago

If what you want is an approximate answer, take a look at * Counting Bloom Filter https://en.wikipedia.org/wiki/Bloom_filter#Counting_filters https://en.wikipedia.org/wiki/Bloom_filter#Counting_filters * Count-Min Sketch https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch Here's a library: https://datasketches.github.io/ https://datasketches.github.io/ However, you can probably fit an exact answer into memory with just a simple hashtable if you've only got 20 million objects. A single byte could be used as the state marker. Either that, or just track 6 counts.