In many scenarios, we can live with approximations in counting.
There are a few techniques in particular which are increasingly being used in online scenarios. Example, services like RedShift, Redis and Spark have in built support for these data structures.
- Hyper Log Log.
- Count Min Sketch.
- Bloom Filters.
- Locality Sensitive Hashing.