4 ms·

So like HyperLogLog?

• qyph 2y ago
  Hyperloglog analyses generally assume access to the full data stream, and so are O(n) at a minimum. Perhaps by running hyperloglog on a sublinear sample of the dataset you'd get an algorithm in this class.
  • doormatt 2y ago
    That makes sense, thanks for explaining!
• dataflow 2y ago
  HyperLogLog uses sublinear space, not sublinear time.