Universal sketches, approximate queries

[ujvl]

• Implement count-min-sketch (supposedly more space-efficient than count-sketch)

• Time-adaptive sketch: decay accuracy & storage for older values (using inflation)

• Integrate with atomic multilog for offline/online approximate queries.

  • Figure out what the basic interface should look like
  • Consider:
    • cross-stream correlation queries
    • use-cases where the same stream is partitioned across multiple servers
    • storage-accuracy tradeoff, blowfish