Approximate collection commands for Redis. Note: I haven't implemented these; I don't have immediate plans to implement these; I don't even know what the right way would be (fork redis? a bunch of Lua scripts? A proxy?); but it was an interesting thing to think about.

approx-redis.md

Approximate set

Unless noted otherwise, these do the same thing their equivalent set commands do. However, only a small fixed amount of memory is used for each set, no matter how many members you add.

• ASADD key member [member ...]
• ASCARD key
  • this will be correct within some small error
• ASINTERCARD key [key ...]
  • this is equivalent to a SINTERSTORE followed by a SCARD, but we can't actually store it
• ASISMEMBER key
  • false positives are possible, false negatives aren't
• ASUNIONSTORE destination key [key...]

(Implementation: HyperLogLog, possibly combined with a bloom filter if we want more accuracy on ASISMEMBER)

Approximate sorted set

Again, unless noted otherwise, these do the same thing their equivalent sorted set commands do, but the amount of space used is fixed, no matter how many members you add.

• AZADD key score member [score member ...]
• AZCARD key
  • correct within some small error
• AZCOUNT key min max
  • this can return lower/upper bounds on the result
• AZINCRBY key increment member
  • increment has to be positive
• AZRANGE key start stop
  • this can only work for small values of start and stop
• AZREVRANGE key start stop
  • this can only work for small values of start and stop
• AZSCORE key member
  • within some error; the true value will be <= the returned value
• AZUNIONSTORE destination numkeys key [key...] [WEIGHTS ...]

(Implementation: Count-Min Sketch, with lists mainted for top and bottom k to allow AZRANGE, plus a q-digest or similar structure to allow AZCOUNT)