Bloom filter

Summary: Bloom filters are a probabilistic data structure that checks for presence of an item in a set

Bloom filter command summary

**10 commands in this group:**

[View all bf commands](https://redis.io/commands/?group=bf)

| Command | Summary | Complexity | Since |
|---------|---------|------------|-------|
| [BF.ADD](https://redis.io/commands/bf.add/) | Adds an item to a Bloom Filter | O(k), where k is the number of hash functions u... | 1.0.0 |
| [BF.CARD](https://redis.io/commands/bf.card/) | Returns the cardinality of a Bloom filter | O(1) | 2.4.4 |
| [BF.EXISTS](https://redis.io/commands/bf.exists/) | Checks whether an item exists in a Bloom Filter | O(k), where k is the number of hash functions u... | 1.0.0 |
| [BF.INFO](https://redis.io/commands/bf.info/) | Returns information about a Bloom Filter | O(1) | 1.0.0 |
| [BF.INSERT](https://redis.io/commands/bf.insert/) | Adds one or more items to a Bloom Filter. A filter will be created if it does not exist | O(k * n), where k is the number of hash functio... | 1.0.0 |
| [BF.LOADCHUNK](https://redis.io/commands/bf.loadchunk/) | Restores a filter previously saved using SCANDUMP | O(n), where n is the capacity | 1.0.0 |
| [BF.MADD](https://redis.io/commands/bf.madd/) | Adds one or more items to a Bloom Filter. A filter will be created if it does not exist | O(k * n), where k is the number of hash functio... | 1.0.0 |
| [BF.MEXISTS](https://redis.io/commands/bf.mexists/) | Checks whether one or more items exist in a Bloom Filter | O(k * n), where k is the number of hash functio... | 1.0.0 |
| [BF.RESERVE](https://redis.io/commands/bf.reserve/) | Creates a new Bloom Filter | O(1) | 1.0.0 |
| [BF.SCANDUMP](https://redis.io/commands/bf.scandump/) | Begins an incremental save of the bloom filter | O(n), where n is the capacity | 1.0.0 |

A Bloom filter is a probabilistic data structure in Redis Open Source that enables you to check if an element is present in a set using a very small memory space of a fixed size.

Instead of storing all the items in a set, a Bloom Filter stores only the items' hashed representations, thus sacrificing some precision. The trade-off is that Bloom Filters are very space-efficient and fast.

A Bloom filter can guarantee the absence of an item from a set, but it can only give an estimation about its presence. So when it responds that an item is not present in a set (a negative answer), you can be sure that indeed is the case. But one out of every N positive answers will be wrong. Even though it looks unusual at first glance, this kind of uncertainty still has its place in computer science. There are many cases out there where a negative answer will prevent more costly operations, for example checking if a username has been taken, if a credit card has been reported as stolen, if a user has already seen an ad and much more.

Use cases

**Financial fraud detection (finance)**

This application answers the question, "Has the user paid from this location before?", thus checking for suspicious activity in their users' shopping habits.

Use one Bloom filter per user, checked for every transaction. Provide an extremely fast response (local latency). Replicate in different regions in case the user moves. Prevent decreasing performance with scale.

Using the Redis Bloom filter for this type of application provides these benefits:

- Fast transaction completion
- Decreased possibility for transaction to break in case of network partitions (connection needs to be kept open for a shorter time)
- Extra layer of security for both credit card owners and retailers

Other questions a Bloom filter can help answer in the finance industry are:

- Has the user ever made purchases in this category of products/services?
- Do I need to skip some security steps when the user is buying with a vetted online shop (big retailers like Amazon, Apple app store...)?
- Has this credit card been reported as lost/stolen? An additional benefit of using a Bloom filter in the last case is that financial organizations can exchange their lists of stolen/blocked credit card numbers without revealing the numbers themselves.

**Ad placement (retail, advertising)**

This application answers these questions:

- Has the user already seen this ad?
- Has the user already bought this product?

Use a Bloom filter for every user, storing all bought products. The recommendation engine suggests a new product and checks if the product is in the user's Bloom filter.

- If no, the ad is shown to the user and is added to the Bloom filter.
- If yes, the process restarts and repeats until it finds a product that is not present in the filter.

Using the Redis Bloom filter for this type of application provides these benefits:

- Cost efficient way to a customized near real-time experience
- No need to invest in expensive infrastructure

**Check if a username is taken (SaaS, content publishing platforms)**

This application answers this question: Has this username/email/domain name/slug already been used?

Use a Bloom filter for every username that has signed up. A new user types in the desired username. The app checks if the username exists in the Bloom filter.

- If no, the user is created and the username is added to the Bloom filter.
- If yes, the app can decide to either check the main database or reject the username.

The query time stays the same at scale.

Using the Redis Bloom filter for this type of application provides these benefits:

- Very fast and efficient way to do a common operation
- No need to invest in expensive infrastructure

Example

Consider a bike manufacturer that makes a million different kinds of bikes and you'd like to avoid using a duplicate model name in new models. A Bloom filter can be used to detect duplicates. In the example that follows,  you'll create a filter with space for a million entries and with a 0.1% error rate. Add one model name and check if it exists. Then add multiple model names and check if they exist.

#### Code Examples

Bloom filter operations: Use BF.RESERVE to create a filter, BF.ADD and BF.MADD to add items, and BF.EXISTS and BF.MEXISTS to check membership when you need space-efficient probabilistic set membership testing

**Difficulty:** Intermediate

**Commands:** BF.RESERVE, BF.ADD, BF.EXISTS, BF.MADD, BF.MEXISTS

**Complexity:**
- BF.RESERVE: O(1)
- BF.ADD: O(k)
- BF.EXISTS: O(k)
- BF.MADD: O(k * n)
- BF.MEXISTS: O(k * n)

**Redis CLI:**

[code example]

**Available in:** Redis CLI, C# (Synchronous), Go, Java (Synchronous - Jedis), JavaScript (Node.js), PHP, Python

**C# (Synchronous):**

[code example]

**Go:**

[code example]

**Java (Synchronous - Jedis):**

[code example]

**JavaScript (Node.js):**

[code example]

**PHP:**

[code example]

**Python:**

[code example]

Note: there is always a chance that even with just a few items, there could be a false positive, meaning an item could "exist" even though it has not been explicitly added to the Bloom filter. For a more in depth understanding of the probabilistic nature of a Bloom filter, check out the blog posts linked at the bottom of this page.

Reserving Bloom filters

With the Redis Bloom filter, most of the sizing work is done for you:

[code example]

#### 1. False positives rate (`error_rate`)
The rate is a decimal value between 0 and 1. For example, for a desired false positive rate of 0.1% (1 in 1000), error_rate should be set to 0.001.

#### 2. Expected capacity (`capacity`)
This is the number of items you expect having in your filter in total and is trivial when you have a static set but it becomes more challenging when your set grows over time. It's important to get the number right because if you **oversize** - you'll end up wasting memory. If you **undersize**, the filter will fill up and a new one will have to be stacked on top of it (sub-filter stacking). In the cases when a filter consists of multiple sub-filters stacked on top of each other latency for adds stays the same, but the latency for presence checks increases. The reason for this is the way the checks work: a regular check would first be performed on the top (latest) filter and if a negative answer is returned the next one is checked and so on. That's where the added latency comes from.

#### 3. Scaling (`EXPANSION`)
Adding an item to a Bloom filter never fails due to the data structure "filling up". Instead, the error rate starts to grow. To keep the error close to the one set on filter initialization, the Bloom filter will auto-scale, meaning, when capacity is reached, an additional sub-filter will be created.
 The size of the new sub-filter is the size of the last sub-filter multiplied by `EXPANSION`. If the number of items to be stored in the filter is unknown, we recommend that you use an expansion of 2 or more to reduce the number of sub-filters. Otherwise, we recommend that you use an expansion of 1 to reduce memory consumption. The default expansion value is 2.

 The filter will keep adding more hash functions for every new sub-filter in order to keep your desired error rate.

Maybe you're wondering "Why would I create a smaller filter with a high expansion rate if I know I'm going to scale anyway?"; the answer is: for cases where you need to keep many filters (let's say a filter per user, or per product) and most of them will stay small, but some with more activity will have to scale.

#### 4. `NONSCALING`
If you know you're not going to scale use the `NONSCALING` flag because that way the filter will use one hash function less. Just remember that if you ever do reach the initially assigned capacity - your error rate will start to grow.

Total size of a Bloom filter

The actual memory used by a Bloom filter is a function of the chosen error rate:

The optimal number of hash functions is `ceil(-ln(error_rate) / ln(2))`.

The required number of bits per item, given the desired `error_rate` and the optimal number of hash functions, is `-ln(error_rate) / ln(2)^2`. Hence, the required number of bits in the filter is `capacity * -ln(error_rate) / ln(2)^2`.

* **1%**    error rate requires  7 hash functions and  9.585 bits per item.
* **0.1%**  error rate requires 10 hash functions and 14.378 bits per item.
* **0.01%** error rate requires 14 hash functions and 19.170 bits per item.

Just as a comparison, when using a Redis set for membership testing the memory needed is:

[code example]

For a set of IP addresses, for example, we would have around 40 bytes (320 bits) per item - considerably higher than the 19.170 bits we need for a Bloom filter with a 0.01% false positives rate.

Bloom vs. Cuckoo filters

Bloom filters typically exhibit better performance and scalability when inserting
items (so if you're often adding items to your dataset, then a Bloom filter may be ideal).
Cuckoo filters are quicker on check operations and also allow deletions.

Performance

Insertion in a Bloom filter is O(K), where `k` is the number of hash functions.

Checking for an item is O(K) or O(K*n) for stacked filters, where n is the number of stacked filters.

Academic sources

- [Space/Time Trade-offs in Hash Coding with Allowable Errors](http://www.dragonwins.com/domains/getteched/bbc/literature/Bloom70.pdf) by Burton H. Bloom.
- [Scalable Bloom Filters](https://gsd.di.uminho.pt/members/cbm/ps/dbloom.pdf)

References

Webinars

1. [Probabilistic Data Structures - The most useful thing in Redis you probably aren't using](https://youtu.be/dq-0xagF7v8?t=102)

Blog posts

1. [RedisBloom Quick Start Tutorial](https://docs.redis.com/latest/modules/redisbloom/redisbloom-quickstart/)
1. [Developing with Bloom Filters](https://redis.io/blog/bloom-filter/)
1. [RedisBloom on Redis Software](https://redis.com/redis-enterprise/redis-bloom/)
1. [Probably and No: Redis, RedisBloom, and Bloom Filters](https://redis.com/blog/redis-redisbloom-bloom-filters/)

> BF.RESERVE bikes:models 0.001 1000000
OK
> BF.ADD bikes:models "Smoky Mountain Striker"
(integer) 1
> BF.EXISTS bikes:models "Smoky Mountain Striker"
(integer) 1
> BF.MADD bikes:models "Rocky Mountain Racer" "Cloudy City Cruiser" "Windy City Wippet"
1) (integer) 1
2) (integer) 1
3) (integer) 1
> BF.MEXISTS bikes:models "Rocky Mountain Racer" "Cloudy City Cruiser" "Windy City Wippet"
1) (integer) 1
2) (integer) 1
3) (integer) 1

bool res1 = db.BF().Reserve("bikes:models", 0.01, 1000);
        Console.WriteLine(res1);    // >>> True

        bool res2 = db.BF().Add("bikes:models", "Smoky Mountain Striker");
        Console.WriteLine(res2);    // >>> True

        bool res3 = db.BF().Exists("bikes:models", "Smoky Mountain Striker");
        Console.WriteLine(res3);    // >>> True

        bool[] res4 = db.BF().MAdd("bikes:models", new RedisValue[]{
            "Rocky Mountain Racer",
            "Cloudy City Cruiser",
            "Windy City Wippet"
        });
        Console.WriteLine(string.Join(", ", res4)); // >>> True, True, True

        bool[] res5 = db.BF().MExists("bikes:models", [
            "Rocky Mountain Racer",
            "Cloudy City Cruiser",
            "Windy City Wippet"
        ]);
        Console.WriteLine(string.Join(", ", res5)); // >>> True, True, True

res1, err := rdb.BFReserve(ctx, "bikes:models", 0.01, 1000).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res1) // >>> OK

	res2, err := rdb.BFAdd(ctx, "bikes:models", "Smoky Mountain Striker").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res2) // >>> true

	res3, err := rdb.BFExists(ctx, "bikes:models", "Smoky Mountain Striker").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res3) // >>> true

	res4, err := rdb.BFMAdd(ctx, "bikes:models",
		"Rocky Mountain Racer",
		"Cloudy City Cruiser",
		"Windy City Wippet",
	).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res4) // >>> [true true true]

	res5, err := rdb.BFMExists(ctx, "bikes:models",
		"Rocky Mountain Racer",
		"Cloudy City Cruiser",
		"Windy City Wippet",
	).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res5) // >>> [true true true]

String res1 = jedis.bfReserve("bikes:models", 0.01, 1000);
        System.out.println(res1); // >>> OK

        boolean res2 = jedis.bfAdd("bikes:models", "Smoky Mountain Striker");
        System.out.println(res2); // >>> True

        boolean res3 = jedis.bfExists("bikes:models", "Smoky Mountain Striker");
        System.out.println(res3); // >>> True

        List<Boolean> res4 = jedis.bfMAdd("bikes:models",
                "Rocky Mountain Racer",
                "Cloudy City Cruiser",
                "Windy City Wippet");
        System.out.println(res4); // >>> [True, True, True]

        List<Boolean> res5 = jedis.bfMExists("bikes:models",
                "Rocky Mountain Racer",
                "Cloudy City Cruiser",
                "Windy City Wippet");
        System.out.println(res5); // >>> [True, True, True]

const res1 = await client.bf.reserve('bikes:models', 0.01, 1000);
console.log(res1);  // >>> OK

const res2 = await client.bf.add('bikes:models', 'Smoky Mountain Striker');
console.log(res2);  // >>> true

const res3 = await client.bf.exists('bikes:models', 'Smoky Mountain Striker');
console.log(res3);  // >>> true

const res4 = await client.bf.mAdd('bikes:models', [
  'Rocky Mountain Racer',
  'Cloudy City Cruiser',
  'Windy City Wippet'
]);
console.log(res4);  // >>> [true, true, true]

const res5 = await client.bf.mExists('bikes:models', [
  'Rocky Mountain Racer',
  'Cloudy City Cruiser',
  'Windy City Wippet'
]);
console.log(res5);  // >>> [true, true, true]

$res1 = $r->bfreserve('bikes:models', 0.01, 1000);
        echo $res1 . PHP_EOL;
        // >>> OK

        $res2 = $r->bfadd('bikes:models', 'Smoky Mountain Striker');
        echo $res2 . PHP_EOL;
        // >>> 1

        $res3 = $r->bfexists('bikes:models', 'Smoky Mountain Striker');
        echo $res3 . PHP_EOL;
        // >>> 1

        $res4 = $r->bfmadd(
            'bikes:models',
            'Rocky Mountain Racer',
            'Cloudy City Cruiser',
            'Windy City Wippet'
        );
        echo json_encode($res4) . PHP_EOL;
        // >>> [1,1,1]

        $res5 = $r->bfmexists(
            'bikes:models',
            'Rocky Mountain Racer',
            'Cloudy City Cruiser',
            'Windy City Wippet'
        );
        echo json_encode($res5) . PHP_EOL;
        // >>> [1,1,1]

res1 = r.bf().reserve("bikes:models", 0.01, 1000)
print(res1)  # >>> True

res2 = r.bf().add("bikes:models", "Smoky Mountain Striker")
print(res2)  # >>> True

res3 = r.bf().exists("bikes:models", "Smoky Mountain Striker")
print(res3)  # >>> True

res4 = r.bf().madd(
    "bikes:models",
    "Rocky Mountain Racer",
    "Cloudy City Cruiser",
    "Windy City Wippet",
)
print(res4)  # >>> [True, True, True]

res5 = r.bf().mexists(
    "bikes:models",
    "Rocky Mountain Racer",
    "Cloudy City Cruiser",
    "Windy City Wippet",
)
print(res5)  # >>> [True, True, True]

BF.RESERVE {key} {error_rate} {capacity} [EXPANSION expansion] [NONSCALING]

memory_with_sets = capacity*(192b + value)


Configuration Parameters

Summary: Redis probabilistic data structures support multiple configuration parameters.

Overview

As of Redis 8 in Redis Open Source (Redis 8), configuration parameters for the probabilistic data structures are now set in the following ways:
* At load time via your `redis.conf` file.
* At run time (where applicable) using the [`CONFIG SET`]() command.

Also, Redis 8 persists probabilistic configuration parameters just like any other configuration parameters (e.g., using the [`CONFIG REWRITE`]() command).

Redis probabilistic data structure configuration parameters

The following table summarizes which Bloom filter configuration parameters can be set at run-time, and compatibility with Redis Software and Redis Cloud.

| Parameter name
(version < 8.0) | Parameter name
(version ≥ 8.0) | Run-time | Redis
Software | Redis
Cloud |
| :------- | :------- | :------- | :------- | :------- |
| ERROR_RATE         | [bf-error-rate](#bf-error-rate)             | :white_check_mark: | ✅ Supported

 | ✅ Flexible & Annual
<nobr>❌ Free & Fixed</nobr> |
|                    | [bf-expansion-factor](#bf-expansion-factor) | :white_check_mark: |||
| INITIAL_SIZE       | [bf-initial-size](#bf-initial-size)         | :white_check_mark: | ✅ Supported

 | ✅ Flexible & Annual
<nobr>❌ Free & Fixed</nobr> |

The following table summarizes which Cuckoo filter configuration parameters can be set at run-time, and compatibility with Redis Software and Redis Cloud.

| Parameter name
(version < 8.0) | Parameter name
(version ≥ 8.0) | Run-time | Redis
Software | Redis
Cloud |
| :------- | :------- | :------- | :------- | :------- |
|                    | [cf-bucket-size](#cf-bucket-size)           | :white_check_mark: |||
|                    | [cf-initial-size](#cf-initial-size)         | :white_check_mark: |||
|                    | [cf-expansion-factor](#cf-expansion-factor) | :white_check_mark: |||
| CF_MAX_EXPANSIONS  | [cf-max-expansions](#cf-max-expansions)     | :white_check_mark: | ✅ Supported

 | ✅ Flexible & Annual
<nobr>❌ Free & Fixed</nobr> |
|                    | [cf-max-iterations](#cf-max-iterations)     | :white_check_mark: |||

Parameter names for Redis Open Source versions < 8.0, while deprecated, will still be supported in Redis 8.

See also [Redis configuration]().

---

A filter should always be sized for the expected capacity and the desired error rate.
Using the `INSERT` family commands with the default values should be used in cases where many small filters exist and the expectation is most will remain at around the default sizes.
Not optimizing a filter for its intended use will result in degradation of performance and memory efficiency.

Default parameters for Bloom filters

bf-error-rate

Default false positive rate for Bloom filters.

Type: double

Valid range: `(0 .. 1)`. Though the valid range is `(0 .. 1)` (corresponding to `> 0%` to `< 100%` false positive rate), any value greater than `0.25` is treated as `0.25`.

Default: `0.01`

bf-expansion-factor

Added in v8.0.0.

Expansion factor for Bloom filters.

Type: integer

Valid range: `[0 .. 32768]`.

Default: `2`

bf-initial-size

Initial capacity for Bloom filters.

Type: integer

Valid range: `[1 .. 1048576]`

Default: `100`

Default parameters for Cuckoo filters

cf-bucket-size

Added in v8.0.0.

The number of items in each Cuckoo filter bucket.

Type: integer

Valid range: `[1 .. 255]`

Default: `2`

cf-initial-size

Added in v8.0.0.

Cuckoo filter initial capacity.

Type: integer

Valid range: `[2*cf-bucket-size .. 1048576]`

Default: `1024`

cf-expansion-factor

Added in v8.0.0.

Expansion factor for Cuckoo filters.

Type: integer

Valid range: `[0 .. 32768]`

Default: `1`

cf-max-expansions

The maximum number of expansions for Cuckoo filters.

Type: integer

Valid range: `[1 .. 65535]`

Default: `32`

cf-max-iterations

Added in v8.0.0

The maximum number of iterations for Cuckoo filters.

Type: integer

Valid range: `[1 .. 65535]`

Default: `20`

Setting configuration parameters on module load (deprecated)

These methods are deprecated beginning with Redis 8.

Setting configuration parameters at load-time is done by appending arguments after the `--loadmodule` argument when starting a server from the command line or after the `loadmodule` directive in a Redis config file. For example:

In [redis.conf]():

[code example]

From the [Redis CLI](), using the [MODULE LOAD]() command:

[code example]

From the command line:

[code example]

127.0.0.6379> MODULE LOAD redisbloom.so [OPT VAL]...

$ redis-server --loadmodule ./redisbloom.so [OPT VAL]...


Count-min sketch

Summary: Count-min sketch is a probabilistic data structure that estimates the frequency of an element in a data stream.

Count-min sketch command summary

**6 commands in this group:**

[View all cms commands](https://redis.io/commands/?group=cms)

| Command | Summary | Complexity | Since |
|---------|---------|------------|-------|
| [CMS.INCRBY](https://redis.io/commands/cms.incrby/) | Increases the count of one or more items by increment | O(n) where n is the number of items | 2.0.0 |
| [CMS.INFO](https://redis.io/commands/cms.info/) | Returns information about a sketch | O(1) | 2.0.0 |
| [CMS.INITBYDIM](https://redis.io/commands/cms.initbydim/) | Initializes a Count-Min Sketch to dimensions specified by user | O(1) | 2.0.0 |
| [CMS.INITBYPROB](https://redis.io/commands/cms.initbyprob/) | Initializes a Count-Min Sketch to accommodate requested tolerances. | O(1) | 2.0.0 |
| [CMS.MERGE](https://redis.io/commands/cms.merge/) | Merges several sketches into one sketch | O(n) where n is the number of sketches | 2.0.0 |
| [CMS.QUERY](https://redis.io/commands/cms.query/) | Returns the count for one or more items in a sketch | O(n) where n is the number of items | 2.0.0 |

Count-Min Sketch is a probabilistic data structure in Redis Open Source that can be used to estimate the frequency of events/elements in a stream of data.

It uses a sub-linear space at the expense of over-counting some events due to collisions. It consumes a stream of events/elements and keeps estimated counters of their frequency.

It is very important to know that the results coming from a Count-Min sketch lower than a certain threshold (determined by the error_rate) should be ignored and often even approximated to zero. So Count-Min sketch is indeed a data-structure for counting frequencies of elements in a stream, but it's only useful for higher counts. Very low counts should be ignored as noise.

Use cases

**Products (retail, online shops)**

This application answers this question: What was the sales volume (on a certain day) for a product?

Use one Count-Min sketch created per day (period). Every product sale goes into the CMS. The CMS give reasonably accurate results for the products that contribute the most toward the sales. Products with low percentage of the total sales are ignored.

Examples

Assume you select an error rate of 0.1% (0.001) with a certainty of 99.8% (0.998). This means you have an error probability of 0.2% (0.002). Your sketch strives to keep the error within 0.1% of the total count of all elements you've added. There's a 0.2% chance the error might exceed this—like when an element below the threshold overlaps with one above it. When you add a few items to the CMS and evaluate their frequency, remember that in such a small sample, collisions are rare, as seen with other probabilistic data structures.

#### Code Examples

Count-min sketch operations: Use CMS.INITBYPROB to create a sketch, CMS.INCRBY to increment element counts, CMS.QUERY to estimate frequencies, and CMS.INFO to inspect sketch properties when you need to estimate element frequencies in a data stream

**Difficulty:** Intermediate

**Commands:** CMS.INITBYPROB, CMS.INCRBY, CMS.QUERY, CMS.INFO

**Complexity:**
- CMS.INITBYPROB: O(1)
- CMS.INCRBY: O(n)
- CMS.QUERY: O(n)
- CMS.INFO: O(1)

**Redis CLI:**

[code example]

**Available in:** Redis CLI, C# (Synchronous), Go, Java (Synchronous - Jedis), JavaScript (Node.js), PHP, Python

**C# (Synchronous):**

[code example]

**Go:**

[code example]

**Java (Synchronous - Jedis):**

[code example]

**JavaScript (Node.js):**

[code example]

**PHP:**

[code example]

**Python:**

[code example]

##### Example 1:
If we had a uniform distribution of 1000 elements where each has a count of around 500 the threshold would be 500:

[code example]

This shows that a CMS is maybe not the best data structure to count frequency of a uniformly distributed stream.
Let's try decreasing the error to 0.01%:

[code example]
This threshold looks more acceptable already, but it means we will need a bigger sketch width `w = 2/error = 20 000` and consequently - more memory.

##### Example 2:
In another example let's imagine a normal (gaussian) distribution where we have 1000 elements, out of which 800 will have a summed count of 400K (with an average count of 500) and 200 elements will have a much higher summed count of 1.6M (with an average count of 8000), making them the heavy hitters (elephant flow). The threshold after "populating" the sketch with all the 1000 elements would be:

[code example]

This threshold seems to be sitting comfortably between the 2 average counts 500 and 8000 so the initial chosen error rate should be working well for this case.

Sizing

Even though the Count-Min sketch is similar to Bloom filter in many ways, its sizing is considerably more complex. The initialisation command receives only two sizing parameters, but you have to understand them thoroughly if you want to have a usable sketch.

[code example]

1. Error

The `error` parameter will determine the width `w` of your sketch and the probability will determine the number of hash functions (depth `d`). The error rate we choose will determine the threshold above which we can trust the result from the sketch. The correlation is:
[code example]
or
[code example]

where `total_count` is the sum of the count of all elements that can be obtained from the `count` key of the result of the [`CMS.INFO`]() command and is of course dynamic - it changes with every new increment in the sketch. At creation time you can approximate the `total_count` ratio as a product of the average count you'll be expecting in the sketch and the average number of elements.

Since the threshold is a function of the total count in the filter it's very important to note that it will grow as  the count grows, but knowing the total count we can always dynamically calculate the threshold. If a result is below it - it can be discarded.

2. Probability

`probability` in this data structure represents the chance of an element that has a count below the threshold to collide with elements that had a count above the threshold on all sketches/depths thus returning a min-count of a frequently occurring element instead of its own.

Performance

Adding, updating and querying for elements in a CMS has a time complexity O(1).

Academic sources

- [An Improved Data Stream Summary: The Count-Min Sketch and its Applications](http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf)

References

- [Count-Min Sketch: The Art and Science of Estimating Stuff](https://redis.com/blog/count-min-sketch-the-art-and-science-of-estimating-stuff/)

> CMS.INITBYPROB bikes:profit 0.001 0.002
OK
> CMS.INCRBY bikes:profit "Smokey Mountain Striker" 100
(integer) 100
> CMS.INCRBY bikes:profit "Rocky Mountain Racer" 200 "Cloudy City Cruiser" 150
1) (integer) 200
2) (integer) 150
> CMS.QUERY bikes:profit "Smokey Mountain Striker" "Rocky Mountain Racer" "Cloudy City Cruiser" "Terrible Bike Name"
1) (integer) 100
2) (integer) 200
3) (integer) 150
4) (integer) 0
> CMS.INFO bikes:profit
1) width
2) (integer) 2000
3) depth
4) (integer) 9
5) count
6) (integer) 450

bool res1 = db.CMS().InitByProb("bikes:profit", 0.001, 0.002);
        Console.WriteLine(res1);    // >>> True

        long res2 = db.CMS().IncrBy("bikes:profit", "Smoky Mountain Striker", 100);
        Console.WriteLine(res2);    // >>> 100

        long[] res3 = db.CMS().IncrBy("bikes:profit",
            [
                new("Rocky Mountain Racer", 200),
                new("Cloudy City Cruiser", 150)
            ]
        );
        Console.WriteLine(string.Join(", ", res3)); // >>> 200, 150

        long[] res4 = db.CMS().Query("bikes:profit", new RedisValue[] { "Smoky Mountain Striker" });
        Console.WriteLine(string.Join(", ", res4)); // >>> 100

        CmsInformation res5 = db.CMS().Info("bikes:profit");
        Console.WriteLine($"Width: {res5.Width}, Depth: {res5.Depth}, Count: {res5.Count}");
        // >>> Width: 2000, Depth: 9, Count: 450

res1, err := rdb.CMSInitByProb(ctx, "bikes:profit", 0.001, 0.002).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res1) // >>> OK

	res2, err := rdb.CMSIncrBy(ctx, "bikes:profit",
		"Smoky Mountain Striker", 100,
	).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res2) // >>> [100]

	res3, err := rdb.CMSIncrBy(ctx, "bikes:profit",
		"Rocky Mountain Racer", 200,
		"Cloudy City Cruiser", 150,
	).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res3) // >>> [200 150]

	res4, err := rdb.CMSQuery(ctx, "bikes:profit",
		"Smoky Mountain Striker",
	).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res4) // >>> [100]

	res5, err := rdb.CMSInfo(ctx, "bikes:profit").Result()

	if err != nil {
		panic(err)
	}

	fmt.Printf("Width: %v, Depth: %v, Count: %v",
		res5.Width, res5.Depth, res5.Count)
	// >>> Width: 2000, Depth: 9, Count: 450

String res1 = jedis.cmsInitByProb("bikes:profit", 0.001d, 0.002d);
    System.out.println(res1); // >>> OK

    long res2 = jedis.cmsIncrBy("bikes:profit", "Smoky Mountain Striker", 100L);
    System.out.println(res2); // >>> 100

    List<Long> res3 = jedis.cmsIncrBy("bikes:profit", new HashMap<String, Long>() {{
      put("Rocky Mountain Racer", 200L);
      put("Cloudy City Cruiser", 150L);
    }});
    System.out.println(res3); // >>> [200, 150]

    List<Long> res4 = jedis.cmsQuery("bikes:profit", "Smoky Mountain Striker");
    System.out.println(res4); // >>> [100]

    Map<String, Object> res5 = jedis.cmsInfo("bikes:profit");
    System.out.println(res5.get("width") + " " + res5.get("depth") + " " + res5.get("count")); // >>> 2000 9 450

const res1 = await client.cms.initByProb('bikes:profit', 0.001, 0.002);
console.log(res1);  // >>> OK

const res2 = await client.cms.incrBy('bikes:profit', {
    item: 'Smoky Mountain Striker',
    incrementBy: 100
});
console.log(res2);  // >>> [100]

const res3 = await client.cms.incrBy('bikes:profit', [
  {
    item: 'Rocky Mountain Racer',
    incrementBy: 200
  },
  {
    item: 'Cloudy City Cruiser',
    incrementBy: 150
  }
]);
console.log(res3);  // >>> [200, 150]

const res4 = await client.cms.query('bikes:profit', 'Smoky Mountain Striker');
console.log(res4);  // >>> [100]

const res5 = await client.cms.info('bikes:profit');
console.log(res5.width, res5.depth, res5.count);  // >>> 2000 9 450

$res1 = $r->cmsinitbyprob('bikes:profit', 0.001, 0.002);
        echo $res1 . PHP_EOL;
        // >>> OK

        $res2 = $r->cmsincrby('bikes:profit', 'Smoky Mountain Striker', 100);
        echo json_encode($res2) . PHP_EOL;
        // >>> [100]

        $res3 = $r->cmsincrby(
            'bikes:profit',
            'Rocky Mountain Racer', 200,
            'Cloudy City Cruiser', 150
        );
        echo json_encode($res3) . PHP_EOL;
        // >>> [200,150]

        $res4 = $r->cmsquery('bikes:profit', 'Smoky Mountain Striker');
        echo json_encode($res4) . PHP_EOL;
        // >>> [100]

        $res5 = $r->cmsinfo('bikes:profit');
        echo $res5['width'] . ' ' . $res5['depth'] . ' ' . $res5['count'] . PHP_EOL;
        // >>> 2000 9 450

res1 = r.cms().initbyprob("bikes:profit", 0.001, 0.002)
print(res1)  # >>> True

res2 = r.cms().incrby("bikes:profit", ["Smoky Mountain Striker"], [100])
print(res2)  # >>> [100]

res3 = r.cms().incrby(
    "bikes:profit", ["Rocky Mountain Racer", "Cloudy City Cruiser"], [200, 150]
)
print(res3)  # >>> [200, 150]

res4 = r.cms().query("bikes:profit", "Smoky Mountain Striker")
print(res4)  # >>> [100]

res5 = r.cms().info("bikes:profit")
print(res5.width, res5.depth, res5.count)  # >>> 2000 9 450

threshold = error * total_count  = 0.001 * (1000*500) = 500

threshold = error * total_count = 0.001 * 2M = 2000


Cuckoo filter

Summary: Cuckoo filters are a probabilistic data structure that checks for presence of an element in a set

Cuckoo filter command summary

**12 commands in this group:**

[View all cf commands](https://redis.io/commands/?group=cf)

| Command | Summary | Complexity | Since |
|---------|---------|------------|-------|
| [CF.ADD](https://redis.io/commands/cf.add/) | Adds an item to a Cuckoo Filter | O(k + i), where k is the number of sub-filters ... | 1.0.0 |
| [CF.ADDNX](https://redis.io/commands/cf.addnx/) | Adds an item to a Cuckoo Filter if the item did not exist previously. | O(k + i), where k is the number of sub-filters ... | 1.0.0 |
| [CF.COUNT](https://redis.io/commands/cf.count/) | Return the number of times an item might be in a Cuckoo Filter | O(k), where k is the number of sub-filters | 1.0.0 |
| [CF.DEL](https://redis.io/commands/cf.del/) | Deletes an item from a Cuckoo Filter | O(k), where k is the number of sub-filters | 1.0.0 |
| [CF.EXISTS](https://redis.io/commands/cf.exists/) | Checks whether one or more items exist in a Cuckoo Filter | O(k), where k is the number of sub-filters | 1.0.0 |
| [CF.INFO](https://redis.io/commands/cf.info/) | Returns information about a Cuckoo Filter | O(1) | 1.0.0 |
| [CF.INSERT](https://redis.io/commands/cf.insert/) | Adds one or more items to a Cuckoo Filter. A filter will be created if it does not exist | O(n * (k + i)), where n is the number of items,... | 1.0.0 |
| [CF.INSERTNX](https://redis.io/commands/cf.insertnx/) | Adds one or more items to a Cuckoo Filter if the items did not exist previously. A filter will be created if it does not exist | O(n * (k + i)), where n is the number of items,... | 1.0.0 |
| [CF.LOADCHUNK](https://redis.io/commands/cf.loadchunk/) | Restores a filter previously saved using SCANDUMP | O(n), where n is the capacity | 1.0.0 |
| [CF.MEXISTS](https://redis.io/commands/cf.mexists/) | Checks whether one or more items exist in a Cuckoo Filter | O(k * n), where k is the number of sub-filters ... | 1.0.0 |
| [CF.RESERVE](https://redis.io/commands/cf.reserve/) | Creates a new Cuckoo Filter | O(1) | 1.0.0 |
| [CF.SCANDUMP](https://redis.io/commands/cf.scandump/) | Begins an incremental save of the bloom filter | O(n), where n is the capacity | 1.0.0 |

A Cuckoo filter, just like a Bloom filter, is a probabilistic data structure in Redis Open Source that enables you to check if an element is present in a set in a very fast and space efficient way, while also allowing for deletions and showing better performance than Bloom in some scenarios.

While the Bloom filter is a bit array with flipped bits at positions decided by the hash function, a Cuckoo filter is an array of buckets, storing fingerprints of the values in one of the buckets at positions decided by the two hash functions. A membership query for item `x` searches the possible buckets for the fingerprint of `x`, and returns true if an identical fingerprint is found. A cuckoo filter's fingerprint size will directly determine the false positive rate.

Use cases

**Targeted ad campaigns (advertising, retail)**

This application answers this question: Has the user signed up for this campaign yet?

Use a Cuckoo filter for every campaign, populated with targeted users' ids. On every visit, the user id is checked against one of the Cuckoo filters.

- If yes, the user has not signed up for campaign. Show the ad.
- If the user clicks ad and signs up, remove the user id from that Cuckoo filter.
- If no, the user has signed up for that campaign. Try the next ad/Cuckoo filter.

**Discount code/coupon validation (retail, online shops)**

This application answers this question: Has this discount code/coupon been used yet?

Use a Cuckoo filter populated with all discount codes/coupons. On every try, the entered code is checked against the filter.

- If no, the coupon is not valid.
- If yes, the coupon can be valid. Check the main database. If valid, remove from Cuckoo filter as `used`.

Note> In addition to these two cases, Cuckoo filters serve very well all the Bloom filter use cases.

Examples

> You'll learn how to create an empty cuckoo filter with an initial capacity for 1,000 items, add items, check their existence, and remove them. Even though the [`CF.ADD`]() command can create a new filter if one isn't present, it might not be optimally sized for your needs. It's better to use the [`CF.RESERVE`]() command to set up a filter with your preferred capacity.

#### Code Examples

Cuckoo filter operations: Use CF.RESERVE to create a filter, CF.ADD to add items, CF.EXISTS to check membership, and CF.DEL to remove items when you need space-efficient probabilistic set membership testing with deletion support

**Difficulty:** Intermediate

**Commands:** CF.RESERVE, CF.ADD, CF.EXISTS, CF.DEL

**Complexity:**
- CF.RESERVE: O(1)
- CF.ADD: O(k + i)
- CF.EXISTS: O(k)
- CF.DEL: O(k)

**Redis CLI:**

[code example]

**Available in:** Redis CLI, C# (Synchronous), Go, Java (Synchronous - Jedis), JavaScript (Node.js), PHP, Python

**C# (Synchronous):**

[code example]

**Go:**

[code example]

**Java (Synchronous - Jedis):**

[code example]

**JavaScript (Node.js):**

[code example]

**PHP:**

[code example]

**Python:**

[code example]

Bloom vs. Cuckoo filters

Bloom filters typically exhibit better performance and scalability when inserting
items (so if you're often adding items to your dataset, then a Bloom filter may be ideal).
Cuckoo filters are quicker on check operations and also allow deletions.

Sizing Cuckoo filters

These are the main parameters and features of a cuckoo filter:

- `p` target false positive rate
- `f` fingerprint length in bits
- `α` fill rate or load factor (0≤α≤1)
- `b` number of entries per bucket
- `m` number of buckets
- `n` number of items
- `C` average bits per item

Let's start by remembering that a cuckoo filter bucket can have multiple entries (where each entry stores one fingerprint). If we end up having all entries occupied with a fingerprint then we won't have empty slots to save new elements and the filter will be declared full, that's why we should always maintain a certain percentage of our cuckoo filter free.
As a result of this the "real" memory cost of an item should include that overhead in addition to the fingerprint size. If `α` is the load factor (fingerprint size / total filter size) and `f` is the number of bits in an entry the amortised space cost `f/α bits`.

When you initialise a new filter you are asked to choose its capacity and bucket size.

[code example]

Choosing the capacity  (`capacity`)

The capacity of a Cuckoo filter is calculated as

[code example]
where `n` is the number of elements you expect to have in your filter, `f` is the fingerprint length in bits which is set to `8` and `α` is the fill factor. So in order to get your filter capacity you must first choose a fill factor. The fill factor will determine the density of your data and of course the memory.
The capacity will be rounded up to the next "power of two (2n)" number.

> Please note that inserting repeated items in a cuckoo filter will try to add them multiple times causing your filter to fill up

Because of how Cuckoo Filters work, the filter is likely to declare itself full before capacity is reached and therefore fill rate will likely never reach 100%.

Choosing the bucket size (`BUCKETSIZE`)

Number of items in each bucket. A higher bucket size value improves the fill rate but also causes a higher error rate and slightly slower performance.

[code example]

When bucket size of 1 is used the fill rate is 55% and false positive error rate is 2/256 ≈ 0.78% **which is the minimal false positive rate you can achieve**. Larger buckets increase the error rate linearly but improve the fill rate of the filter. For example, a bucket size of 3 yields a 2.34% error rate and an 80% fill rate. Bucket size of 4 yields a 3.12% error rate and a 95% fill rate.

Choosing the scaling factor (`EXPANSION`)

When the filter self-declares itself full, it will auto-expand by generating additional sub-filters at the cost of reduced performance and increased error rate. The new sub-filter is created with size of the previous sub-filter multiplied by `EXPANSION` (chosen on filter creation). Like bucket size, additional sub-filters grow the error rate linearly (the compound error is a sum of all subfilters' errors). The size of the new sub-filter is the size of the last sub-filter multiplied by expansion and this is something very important to keep in mind. If you know you'll have to scale at some point it's better to choose a higher expansion value. The default is [`cf-expansion-factor`]().

Maybe you're wondering "Why would I create a smaller filter with a high expansion rate if I know I'm going to scale anyway?"; the answer is: for cases where you need to keep many filters (let's say a filter per user, or per product) and most of them will stay small, but some with more activity will have to scale.

The expansion factor will be rounded up to the next "power of two (2n)" number.

Choosing the maximum number of iterations (`MAXITERATIONS`)

`MAXITERATIONS` dictates the number of attempts to find a slot for the incoming fingerprint. Once the filter gets full, a high MAXITERATIONS value will slow down insertions. The default value is [`cf-max-iterations`]().

Interesting facts:

- Unused capacity in prior sub-filters is automatically used when possible.
- The filter can grow up to [`cf-max-expansions`]() times.
- You can delete items to stay within filter limits instead of rebuilding
- Adding the same element multiple times will create multiple entries, thus filling up your filter.

Performance

Adding an element to a Cuckoo filter has a time complexity of O(1).

Similarly, checking for an element and deleting an element also has a time complexity of O(1).

Academic sources

- [Cuckoo Filter: Practically Better Than Bloom](https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf)

> CF.RESERVE bikes:models 1000
OK
> CF.ADD bikes:models "Smoky Mountain Striker"
(integer) 1
> CF.EXISTS bikes:models "Smoky Mountain Striker"
(integer) 1
> CF.EXISTS bikes:models "Terrible Bike Name"
(integer) 0
> CF.DEL bikes:models "Smoky Mountain Striker"
(integer) 1

bool res1 = db.CF().Reserve("bikes:models", 1000000);
        Console.WriteLine(res1);    // >>> True

        bool res2 = db.CF().Add("bikes:models", "Smoky Mountain Striker");
        Console.WriteLine(res2);    // >>> True

        bool res3 = db.CF().Exists("bikes:models", "Smoky Mountain Striker");
        Console.WriteLine(res3);    // >>> True

        bool res4 = db.CF().Exists("bikes:models", "Terrible Bike Name");
        Console.WriteLine(res4);    // >>> False

        bool res5 = db.CF().Del("bikes:models", "Smoky Mountain Striker");
        Console.WriteLine(res5);    // >>> True

res1, err := rdb.CFReserve(ctx, "bikes:models", 1000000).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res1) // >>> OK

	res2, err := rdb.CFAdd(ctx, "bikes:models", "Smoky Mountain Striker").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res2) // >>> true

	res3, err := rdb.CFExists(ctx, "bikes:models", "Smoky Mountain Striker").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res3) // >>> true

	res4, err := rdb.CFExists(ctx, "bikes:models", "Terrible Bike Name").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res4) // >>> false

	res5, err := rdb.CFDel(ctx, "bikes:models", "Smoky Mountain Striker").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res5) // >>> true

String res1 = jedis.cfReserve("bikes:models", 1000000);
        System.out.println(res1); // >>> OK

        boolean res2 = jedis.cfAdd("bikes:models", "Smoky Mountain Striker");
        System.out.println(res2); // >>> True

        boolean res3 = jedis.cfExists("bikes:models", "Smoky Mountain Striker");
        System.out.println(res3); // >>> True

        boolean res4 = jedis.cfExists("bikes:models", "Terrible Bike Name");
        System.out.println(res4); // >>> False

        boolean res5 = jedis.cfDel("bikes:models", "Smoky Mountain Striker");
        System.out.println(res5); // >>> True

const res1 = await client.cf.reserve('bikes:models', 1000000);
console.log(res1);  // >>> OK

const res2 = await client.cf.add('bikes:models', 'Smoky Mountain Striker');
console.log(res2);  // >>> true

const res3 = await client.cf.exists('bikes:models', 'Smoky Mountain Striker');
console.log(res3);  // >>> true

const res4 = await client.cf.exists('bikes:models', 'Terrible Bike Name');
console.log(res4);  // >>> false

const res5 = await client.cf.del('bikes:models', 'Smoky Mountain Striker');
console.log(res5);  // >>> true

$res1 = $r->cfreserve('bikes:models', 1000000);
        echo $res1 . PHP_EOL;
        // >>> OK

        $res2 = $r->cfadd('bikes:models', 'Smoky Mountain Striker');
        echo $res2 . PHP_EOL;
        // >>> 1

        $res3 = $r->cfexists('bikes:models', 'Smoky Mountain Striker');
        echo $res3 . PHP_EOL;
        // >>> 1

        $res4 = $r->cfexists('bikes:models', 'Terrible Bike Name');
        echo $res4 . PHP_EOL;
        // >>> 0

        $res5 = $r->cfdel('bikes:models', 'Smoky Mountain Striker');
        echo $res5 . PHP_EOL;
        // >>> 1

res1 = r.cf().reserve("bikes:models", 1000000)
print(res1)  # >>> True

res2 = r.cf().add("bikes:models", "Smoky Mountain Striker")
print(res2)  # >>> 1

res3 = r.cf().exists("bikes:models", "Smoky Mountain Striker")
print(res3)  # >>> 1

res4 = r.cf().exists("bikes:models", "Terrible Bike Name")
print(res4)  # >>> 0

res5 = r.cf().delete("bikes:models", "Smoky Mountain Striker")
print(res5)  # >>> 1

CF.RESERVE {key} {capacity} [BUCKETSIZE bucketSize] [MAXITERATIONS maxIterations]
[EXPANSION expansion]

error_rate = (buckets * hash_functions)/2^fingerprint_size = (buckets*2)/256


HyperLogLog

Summary: HyperLogLog is a probabilistic data structure that estimates the cardinality of a set.

HyperLogLog command summary

**5 commands in this group:**

[View all hyperloglog commands](https://redis.io/commands/?group=hyperloglog)

| Command | Summary | Complexity | Since |
|---------|---------|------------|-------|
| [PFADD](https://redis.io/commands/pfadd/) | Adds elements to a HyperLogLog key. Creates the key if it doesn't exist. | O(1) to add every element. | 2.8.9 |
| [PFCOUNT](https://redis.io/commands/pfcount/) | Returns the approximated cardinality of the set(s) observed by the HyperLogLog key(s). | O(1) with a very small average constant time wh... | 2.8.9 |
| [PFDEBUG](https://redis.io/commands/pfdebug/) | Internal commands for debugging HyperLogLog values. | N/A | 2.8.9 |
| [PFMERGE](https://redis.io/commands/pfmerge/) | Merges one or more HyperLogLog values into a single key. | O(N) to merge N HyperLogLogs, but with high con... | 2.8.9 |
| [PFSELFTEST](https://redis.io/commands/pfselftest/) | An internal command for testing HyperLogLog values. | N/A | 2.8.9 |

HyperLogLog is a probabilistic data structure that estimates the cardinality of a set, trading perfect accuracy for efficient space utilization. The Redis implementation uses up to 12 KB of memory and provides a standard error rate of 0.81%.

Counting unique items usually requires an amount of memory
proportional to the number of items you want to count, because you need
to remember the elements you have already seen in the past in order to avoid
counting them multiple times. However, a set of algorithms exist that trade
memory for precision: they return an estimated measure with a standard error,
which, in the case of the Redis implementation for HyperLogLog, is less than 1%.
The magic of this algorithm is that you no longer need to use an amount of memory
proportional to the number of items counted, and instead can use a
constant amount of memory; 12k bytes in the worst case, or a lot less if your
HyperLogLog (We'll just call them HLL from now) has seen very few elements.

HLLs in Redis, while technically a different data structure, are encoded
as a Redis string, so you can call [`GET`]() to serialize a HLL, and [`SET`]()
to deserialize it back to the server.

Conceptually the HLL API is like using Sets to do the same task. You would
[`SADD`]() every observed element into a set, and would use [`SCARD`]() to check the
number of elements inside the set, which are unique since [`SADD`]() will not
re-add an existing element.

While you don't really *add items* into an HLL, because the data structure
only contains a state that does not include actual elements, the API is the
same:

* Every time you see a new element, you add it to the count with [`PFADD`]().
* When you want to retrieve the current approximation of unique elements added using the [`PFADD`]() command, you can use the [`PFCOUNT`]() command. If you need to merge two different HLLs, the [`PFMERGE`]() command is available. Since HLLs provide approximate counts of unique elements, the result of the merge will give you an approximation of the number of unique elements across both source HLLs.

#### Code Examples

HyperLogLog operations: Use PFADD to add items to a HyperLogLog, PFCOUNT to estimate cardinality, and PFMERGE to combine HyperLogLogs when you need space-efficient cardinality estimation

**Difficulty:** Intermediate

**Commands:** PFADD, PFCOUNT, PFMERGE

**Complexity:**
- PFADD: O(1)
- PFCOUNT: O(1)
- PFMERGE: O(N)

**Redis CLI:**

[code example]

**Available in:** Redis CLI, C# (Synchronous), Go, Java (Synchronous - Jedis), JavaScript (Node.js), PHP, Python

**C# (Synchronous):**

[code example]

**Go:**

[code example]

**Java (Synchronous - Jedis):**

[code example]

**JavaScript (Node.js):**

[code example]

**PHP:**

[code example]

**Python:**

[code example]

Some examples of use cases for this data structure is counting unique queries
performed by users in a search form every day, number of unique visitors to a web page and other similar cases.

Redis is also able to perform the union of HLLs, please check the
[full documentation]() for more information.

Use cases

**Anonymous unique visits of a web page (SaaS, analytics tools)**

This application answers these questions:

- How many unique visits has this page had on this day?
- How many unique users have played this song?
- How many unique users have viewed this video?

Storing the IP address or any other kind of personal identifier is against the law in some countries, which makes it impossible to get unique visitor statistics on your website.

One HyperLogLog is created per page (video/song) per period, and every IP/identifier is added to it on every visit.

Performance

Writing ([`PFADD`]()) to and reading from ([`PFCOUNT`]()) the HyperLogLog is done in constant time and space.
Merging HLLs is O(n), where _n_ is the number of sketches.

Limits

The HyperLogLog can estimate the cardinality of sets with up to 18,446,744,073,709,551,616 (2^64) members.

Learn more

* [Redis new data structure: the HyperLogLog](http://antirez.com/news/75) has a lot of details about the data structure and its implementation in Redis.
* [Redis HyperLogLog Explained](https://www.youtube.com/watch?v=MunL8nnwscQ) shows you how to use Redis HyperLogLog data structures to build a traffic heat map.

> PFADD bikes Hyperion Deimos Phoebe Quaoar
(integer) 1
> PFCOUNT bikes
(integer) 4
> PFADD commuter_bikes Salacia Mimas Quaoar
(integer) 1
> PFMERGE all_bikes bikes commuter_bikes
OK
> PFCOUNT all_bikes
(integer) 6

bool res1 = db.HyperLogLogAdd("{bikes}", ["Hyperion", "Deimos", "Phoebe", "Quaoar"]);
        Console.WriteLine(res1);    // >>> True

        long res2 = db.HyperLogLogLength("{bikes}");
        Console.WriteLine(res2);    // >>> 4

        bool res3 = db.HyperLogLogAdd("commuter_{bikes}", ["Salacia", "Mimas", "Quaoar"]);
        Console.WriteLine(res3);    // >>> True

        db.HyperLogLogMerge("all_{bikes}", "{bikes}", "commuter_{bikes}");
        long res4 = db.HyperLogLogLength("all_{bikes}");
        Console.WriteLine(res4);    // >>> 6

res1, err := rdb.PFAdd(ctx, "bikes", "Hyperion", "Deimos", "Phoebe", "Quaoar").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res1) // 1

	res2, err := rdb.PFCount(ctx, "bikes").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res2) // 4

	res3, err := rdb.PFAdd(ctx, "commuter_bikes", "Salacia", "Mimas", "Quaoar").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res3) // 1

	res4, err := rdb.PFMerge(ctx, "all_bikes", "bikes", "commuter_bikes").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res4) // OK

	res5, err := rdb.PFCount(ctx, "all_bikes").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res5) // 6

long res1 = jedis.pfadd("bikes", "Hyperion", "Deimos", "Phoebe", "Quaoar");
        System.out.println(res1); // >>> 1

        long res2 = jedis.pfcount("bikes");
        System.out.println(res2); // >>> 4

        long res3 = jedis.pfadd("commuter_bikes", "Salacia", "Mimas", "Quaoar");
        System.out.println(res3); // >>> 1

        String res4 = jedis.pfmerge("all_bikes", "bikes", "commuter_bikes");
        System.out.println(res4); // >>> OK

        long res5 = jedis.pfcount("all_bikes");
        System.out.println(res5); // >>> 6

const res1 = await client.pfAdd('bikes', ['Hyperion', 'Deimos', 'Phoebe', 'Quaoar']);
console.log(res1);  // >>> 1

const res2 = await client.pfCount('bikes');
console.log(res2);  // >>> 4

const res3 = await client.pfAdd('commuter_bikes', ['Salacia', 'Mimas', 'Quaoar']);
console.log(res3);  // >>> 1

const res4 = await client.pfMerge('all_bikes', ['bikes', 'commuter_bikes']);
console.log(res4);  // >>> OK

const res5 = await client.pfCount('all_bikes');
console.log(res5);  // >>> 6

$res1 = $r->pfadd('bikes', ['Hyperion', 'Deimos', 'Phoebe', 'Quaoar']);
        echo $res1 . PHP_EOL;
        // >>> 1

        $res2 = $r->pfcount('bikes');
        echo $res2 . PHP_EOL;
        // >>> 4

        $res3 = $r->pfadd('commuter_bikes', ['Salacia', 'Mimas', 'Quaoar']);
        echo $res3 . PHP_EOL;
        // >>> 1

        $res4 = $r->pfmerge('all_bikes', 'bikes', 'commuter_bikes');
        echo $res4 . PHP_EOL;
        // >>> OK

        $res5 = $r->pfcount('all_bikes');
        echo $res5 . PHP_EOL;
        // >>> 6

res1 = r.pfadd("bikes", "Hyperion", "Deimos", "Phoebe", "Quaoar")
print(res1)  # >>> 1

res2 = r.pfcount("bikes")
print(res2)  # >>> 4

res3 = r.pfadd("commuter_bikes", "Salacia", "Mimas", "Quaoar")
print(res3)  # >>> 1

res4 = r.pfmerge("all_bikes", "bikes", "commuter_bikes")
print(res4)  # >>> True

res5 = r.pfcount("all_bikes")
print(res5)  # >>> 6


Probabilistic

Summary: Probabilistic data structures in Redis

HyperLogLog

Bloom filter

Cuckoo filter

Summary: t-digest is a probabilistic data structure that allows you to estimate the percentile of a data stream.

t-digest

Summary: Top-K is a probabilistic data structure that allows you to find the most frequent items in a data stream.

Top-K

Count-min sketch

Configuration Parameters

Content

*Probabilistic data structures* give approximations of statistics such as
counts, frequencies, and rankings rather than precise values.
The advantage of using approximations is that they are adequate for
many common purposes but are much more efficient to calculate. They
sometimes have other advantages too, such as obfuscating times, locations,
and other sensitive data.

Probabilistic data structures are available as part of Redis Open Source and they are available in Redis Software and Redis Cloud.
See
[Install Redis Open Source]() or
[Install Redis Software]()
for full installation instructions.


t-digest

t-digest command summary

**14 commands in this group:**

[View all tdigest commands](https://redis.io/commands/?group=tdigest)

| Command | Summary | Complexity | Since |
|---------|---------|------------|-------|
| [TDIGEST.ADD](https://redis.io/commands/tdigest.add/) | Adds one or more observations to a t-digest sketch | O(N), where N is the number of samples to add | 2.4.0 |
| [TDIGEST.BYRANK](https://redis.io/commands/tdigest.byrank/) | Returns, for each input rank, an estimation of the value (floating-point) with that rank | O(N) where N is the number of ranks specified | 2.4.0 |
| [TDIGEST.BYREVRANK](https://redis.io/commands/tdigest.byrevrank/) | Returns, for each input reverse rank, an estimation of the value (floating-point) with that reverse rank | O(N) where N is the number of reverse ranks spe... | 2.4.0 |
| [TDIGEST.CDF](https://redis.io/commands/tdigest.cdf/) | Returns, for each input value, an estimation of the fraction (floating-point) of (observations smaller than the given value + half the observations equal to the given value) | O(1) | 2.4.0 |
| [TDIGEST.CREATE](https://redis.io/commands/tdigest.create/) | Allocates memory and initializes a new t-digest sketch | O(1) | 2.4.0 |
| [TDIGEST.INFO](https://redis.io/commands/tdigest.info/) | Returns information and statistics about a t-digest sketch | O(1) | 2.4.0 |
| [TDIGEST.MAX](https://redis.io/commands/tdigest.max/) | Returns the maximum observation value from a t-digest sketch | O(1) | 2.4.0 |
| [TDIGEST.MERGE](https://redis.io/commands/tdigest.merge/) | Merges multiple t-digest sketches into a single sketch | O(N*K), where N is the number of centroids and ... | 2.4.0 |
| [TDIGEST.MIN](https://redis.io/commands/tdigest.min/) | Returns the minimum observation value from a t-digest sketch | O(1) | 2.4.0 |
| [TDIGEST.QUANTILE](https://redis.io/commands/tdigest.quantile/) | Returns, for each input fraction, an estimation of the value (floating point) that is smaller than the given fraction of observations | O(N) where N is the number of quantiles specified. | 2.4.0 |
| [TDIGEST.RANK](https://redis.io/commands/tdigest.rank/) | Returns, for each input value (floating-point), the estimated rank of the value (the number of observations in the sketch that are smaller than the value + half the number of observations that are equal to the value) | O(N) where N is the number of values specified. | 2.4.0 |
| [TDIGEST.RESET](https://redis.io/commands/tdigest.reset/) | Resets a t-digest sketch: empty the sketch and re-initializes it. | O(1) | 2.4.0 |
| [TDIGEST.REVRANK](https://redis.io/commands/tdigest.revrank/) | Returns, for each input value (floating-point), the estimated reverse rank of the value (the number of observations in the sketch that are larger than the value + half the number of observations that are equal to the value) | O(N) where N is the number of values specified. | 2.4.0 |
| [TDIGEST.TRIMMED_MEAN](https://redis.io/commands/tdigest.trimmed_mean/) | Returns an estimation of the mean value from the sketch, excluding observation values outside the low and high cutoff quantiles | O(N) where N is the number of centroids | 2.4.0 |

The t-digest is a sketch data structure in Redis Open Source for estimating percentiles from a data stream or a large dataset using a compact sketch.

It can answer questions like:
- Which fraction of the values in the data stream are smaller than a given value?
- How many values in the data stream are smaller than a given value?
- What's the highest value that's smaller than *p* percent of the values in the data stream? (what is the p-percentile value)?

What is t-digest?

t-digest is a data structure that will estimate a percentile point without having to store and order all the data points in a set. For example: to answer the question "What's the average latency for 99% of my database operations" we would have to store the average latency for every user, order the values, cut out the last 1% and only then find the average value of all the rest. This kind of process is costly not just in terms of the processing needed to order those values but also in terms of the space needed to store them. Those are precisely the problems t-digest solves.

t-digest can also be used to estimate other values related to percentiles, like trimmed means.

> A **trimmed mean** is the mean value from the sketch, excluding observation values outside the low and high cutoff percentiles. For example, a 0.1 trimmed mean is the mean value of the sketch, excluding the lowest 10% and the highest 10% of the values.

Use cases

**Hardware/software monitoring**

You measure your online server response latency, and you like to query:

- What are the 50th, 90th, and 99th percentiles of the measured latencies?

- Which fraction of the measured latencies are less than 25 milliseconds?

- What is the mean latency, ignoring outliers? or What is the mean latency between the 10th and the 90th percentile?

**Online gaming**

Millions of people are playing a game on your online gaming platform, and you want to give the following information to each player?

- Your score is better than x percent of the game sessions played.

- There were about y game sessions where people scored larger than you.

- To have a better score than 90% of the games played, your score should be z.

**Network traffic monitoring**

You measure the IP packets transferred over your network each second and try to detect denial-of-service attacks by asking:

- Does the number of packets in the last second exceed 99% of previously observed values?

- How many packets do I expect to see under _normal_ network conditions?
(Answer: between x and y, where x represents the 1st percentile and y represents the 99th percentile).

**Predictive maintenance**

- Was the measured parameter (noise level, current consumption, etc.) irregular? (not within the [1st percentile...99th percentile] range)?

- To which values should I set my alerts?

Examples

In the following example, you'll create a t-digest with a compression of 100 and add items to it. The `COMPRESSION` argument is used to specify the tradeoff between accuracy and memory consumption. The default value is 100. Higher values mean more accuracy. Note: unlike some of the other probabilistic data structures, the [`TDIGEST.ADD`]() command will not create a new structure if the key does not exist.

#### Code Examples

t-digest creation and data addition: Use TDIGEST.CREATE to initialize a sketch and TDIGEST.ADD to insert values when you need to build a percentile estimation data structure

**Commands:** TDIGEST.CREATE, TDIGEST.ADD

**Complexity:**
- TDIGEST.CREATE: O(1)
- TDIGEST.ADD: O(N)

**Redis CLI:**

[code example]

**Available in:** Redis CLI, C# (Synchronous), Go, Java (Synchronous - Jedis), JavaScript (Node.js), PHP, Python

**C# (Synchronous):**

[code example]

**Go:**

[code example]

**Java (Synchronous - Jedis):**

[code example]

**JavaScript (Node.js):**

[code example]

**PHP:**

[code example]

**Python:**

[code example]

You can repeat calling [TDIGEST.ADD]() whenever new observations are available

#### Estimating fractions or ranks by values

Another helpful feature in t-digest is CDF (definition of rank) which gives us the fraction of observations smaller or equal to a certain value. This command is very useful to answer questions like "*What's the percentage of observations with a value lower or equal to X*".

>More precisely, [`TDIGEST.CDF`]() will return the estimated fraction of observations in the sketch that are smaller than X plus half the number of observations that are equal to X. We can also use the [`TDIGEST.RANK`]() command, which is very similar. Instead of returning a fraction, it returns the ----estimated---- rank of a value. The [`TDIGEST.RANK`]() command is also variadic, meaning you can use a single command to retrieve estimations for one or more values.

Here's an example. Given a set of biker's ages, you can ask a question like "What's the percentage of bike racers that are younger than 50 years?"

#### Code Examples

Percentile rank estimation: Use TDIGEST.CDF to estimate the fraction of values below a threshold and TDIGEST.RANK to estimate the rank of values when you need to determine percentile positions

**Difficulty:** Intermediate

**Builds upon:** tdig_start

**Commands:** TDIGEST.CREATE, TDIGEST.ADD, TDIGEST.CDF, TDIGEST.RANK

**Complexity:**
- TDIGEST.CREATE: O(1)
- TDIGEST.ADD: O(N)
- TDIGEST.CDF: O(1)
- TDIGEST.RANK: O(N)

**Redis CLI:**

[code example]

**Available in:** Redis CLI, C# (Synchronous), Go, Java (Synchronous - Jedis), JavaScript (Node.js), PHP, Python

**C# (Synchronous):**

[code example]

**Go:**

[code example]

**Java (Synchronous - Jedis):**

[code example]

**JavaScript (Node.js):**

[code example]

**PHP:**

[code example]

**Python:**

[code example]

And lastly, `TDIGEST.REVRANK key value...` is similar to [TDIGEST.RANK](), but returns, for each input value, an estimation of the number of (observations larger than a given value + half the observations equal to the given value).

#### Estimating values by fractions or ranks

`TDIGEST.QUANTILE key fraction...` returns, for each input fraction, an estimation of the value (floating point) that is smaller than the given fraction of observations. `TDIGEST.BYRANK key rank...` returns, for each input rank, an estimation of the value (floating point) with that rank.

#### Code Examples

Quantile and rank value estimation: Use TDIGEST.QUANTILE to find values at specific percentiles and TDIGEST.BYRANK to find values by rank when you need to retrieve percentile values from a sketch

**Difficulty:** Intermediate

**Builds upon:** tdig_cdf

**Commands:** TDIGEST.QUANTILE, TDIGEST.BYRANK

**Complexity:**
- TDIGEST.QUANTILE: O(N)
- TDIGEST.BYRANK: O(N)

**Redis CLI:**

[code example]

**Available in:** Redis CLI, C# (Synchronous), Go, Java (Synchronous - Jedis), JavaScript (Node.js), PHP, Python

**C# (Synchronous):**

[code example]

**Go:**

[code example]

**Java (Synchronous - Jedis):**

[code example]

**JavaScript (Node.js):**

[code example]

**PHP:**

[code example]

**Python:**

[code example]

`TDIGEST.BYREVRANK key rank...` returns, for each input **reverse rank**, an estimation of the **value** (floating point) with that reverse rank.

#### Estimating trimmed mean

Use `TDIGEST.TRIMMED_MEAN key lowFraction highFraction` to retrieve an estimation of the mean value between the specified fractions.

This is especially useful for calculating the average value ignoring outliers. For example - calculating the average value between the 20th percentile and the 80th percentile.

#### Merging sketches

Sometimes it is useful to merge sketches. For example, suppose we measure latencies for 3 servers, and we want to calculate the 90%, 95%, and 99% latencies for all the servers combined.

`TDIGEST.MERGE destKey numKeys sourceKey... [COMPRESSION compression] [OVERRIDE]` merges multiple sketches into a single sketch.

If `destKey` does not exist - a new sketch is created.

If `destKey` is an existing sketch, its values are merged with the values of the source keys. To override the destination key contents, use `OVERRIDE`.

#### Retrieving sketch information

Use [`TDIGEST.MIN`]() and [`TDIGEST.MAX`]() to retrieve the minimal and maximal values in the sketch, respectively.

#### Code Examples

Sketch metadata retrieval: Use TDIGEST.MIN and TDIGEST.MAX to retrieve the minimum and maximum values in a sketch when you need to inspect the bounds of your data

**Builds upon:** tdig_cdf

**Commands:** TDIGEST.MIN, TDIGEST.MAX

**Complexity:**
- TDIGEST.MIN: O(1)
- TDIGEST.MAX: O(1)

**Redis CLI:**

[code example]

**Available in:** Redis CLI, C# (Synchronous), Go, Java (Synchronous - Jedis), JavaScript (Node.js), PHP, Python

**C# (Synchronous):**

[code example]

**Go:**

[code example]

**Java (Synchronous - Jedis):**

[code example]

**JavaScript (Node.js):**

[code example]

**PHP:**

[code example]

**Python:**

[code example]

Both return `nan` when the sketch is empty.

Both commands return accurate results and are equivalent to `TDIGEST.BYRANK racer_ages 0` and `TDIGEST.BYREVRANK racer_ages 0`, respectively.

Use `TDIGEST.INFO racer_ages` to retrieve some additional information about the sketch.

#### Resetting a sketch

#### Code Examples

Sketch reset: Use TDIGEST.RESET to clear all data from a sketch when you need to reuse a sketch for new data

**Builds upon:** tdig_cdf

**Commands:** TDIGEST.RESET

**Complexity:**
- TDIGEST.RESET: O(1)

**Redis CLI:**

[code example]

**Available in:** Redis CLI, C# (Synchronous), Go, Java (Synchronous - Jedis), JavaScript (Node.js), PHP, Python

**C# (Synchronous):**

[code example]

**Go:**

[code example]

**Java (Synchronous - Jedis):**

[code example]

**JavaScript (Node.js):**

[code example]

**PHP:**

[code example]

**Python:**

[code example]

Academic sources

- [The _t_-digest: Efficient estimates of distributions](https://www.sciencedirect.com/science/article/pii/S2665963820300403)

References

- [t-digest: A New Probabilistic Data Structure in Redis Stack](https://redis.com/blog/t-digest-in-redis-stack/)

> TDIGEST.CREATE bikes:sales COMPRESSION 100
OK
> TDIGEST.ADD bikes:sales 21
OK
> TDIGEST.ADD bikes:sales 150 95 75 34
OK

bool res1 = db.TDIGEST().Create("bikes:sales", 100);
        Console.WriteLine(res1);    // >>> True

        bool res2 = db.TDIGEST().Add("bikes:sales", 21);
        Console.WriteLine(res2);    // >>> True

        bool res3 = db.TDIGEST().Add("bikes:sales", 150, 95, 75, 34);
        Console.WriteLine(res3);    // >>> true

res1, err := rdb.TDigestCreate(ctx, "bikes:sales").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res1) // >>> OK

	res2, err := rdb.TDigestAdd(ctx, "bikes:sales", 21).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res2) // >>> OK

	res3, err := rdb.TDigestAdd(ctx, "bikes:sales",
		150, 95, 75, 34,
	).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res3) // >>> OK

String res1 = jedis.tdigestCreate("bikes:sales", 100);
        System.out.println(res1); // >>> True

        String res2 = jedis.tdigestAdd("bikes:sales", 21);
        System.out.println(res2); // >>> OK

        String res3 = jedis.tdigestAdd("bikes:sales", 150, 95, 75, 34);
        System.out.println(res3); // >>> OK

const res1 = await client.tDigest.create('bikes:sales', 100);
console.log(res1);  // >>> OK

const res2 = await client.tDigest.add('bikes:sales', [21]);
console.log(res2);  // >>> OK

const res3 = await client.tDigest.add('bikes:sales', [150, 95, 75, 34]);
console.log(res3);  // >>> OK

$res1 = $r->tdigestcreate('bikes:sales', 100);
        echo $res1 . PHP_EOL;
        // >>> OK

        $res2 = $r->tdigestadd('bikes:sales', 21);
        echo $res2 . PHP_EOL;
        // >>> OK

        $res3 = $r->tdigestadd('bikes:sales', 150, 95, 75, 34);
        echo $res3 . PHP_EOL;
        // >>> OK

res1 = r.tdigest().create("bikes:sales", 100)
print(res1)  # >>> True

res2 = r.tdigest().add("bikes:sales", [21])
print(res2)  # >>> OK

res3 = r.tdigest().add("bikes:sales", [150, 95, 75, 34])
print(res3)  # >>> OK

> TDIGEST.CREATE racer_ages
OK
> TDIGEST.ADD racer_ages 45.88 44.2 58.03 19.76 39.84 69.28 50.97 25.41 19.27 85.71 42.63
OK
> TDIGEST.CDF racer_ages 50
1) "0.63636363636363635"
> TDIGEST.RANK racer_ages 50
1) (integer) 7
> TDIGEST.RANK racer_ages 50 40
1) (integer) 7
2) (integer) 4

bool res4 = db.TDIGEST().Create("racer_ages");
        Console.WriteLine(res4);    // >>> True

        bool res5 = db.TDIGEST().Add("racer_ages",
            45.88,
            44.2,
            58.03,
            19.76,
            39.84,
            69.28,
            50.97,
            25.41,
            19.27,
            85.71,
            42.63
        );
        Console.WriteLine(res5);    // >>> True

        long[] res6 = db.TDIGEST().Rank("racer_ages", 50);
        Console.WriteLine(string.Join(", ", res6)); // >>> 7

        long[] res7 = db.TDIGEST().Rank("racer_ages", 50, 40);
        Console.WriteLine(string.Join(", ", res7)); // >>> 7, 4

res4, err := rdb.TDigestCreate(ctx, "racer_ages").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res4) // >>> OK

	res5, err := rdb.TDigestAdd(ctx, "racer_ages",
		45.88, 44.2, 58.03, 19.76, 39.84, 69.28,
		50.97, 25.41, 19.27, 85.71, 42.63,
	).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res5) // >>> OK

	res6, err := rdb.TDigestRank(ctx, "racer_ages", 50).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res6) // >>> [7]

	res7, err := rdb.TDigestRank(ctx, "racer_ages", 50, 40).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res7) // >>> [7 4]

String res4 = jedis.tdigestCreate("racer_ages");
        System.out.println(res4); // >>> True

        String res5 = jedis.tdigestAdd("racer_ages", 45.88,
                44.2,
                58.03,
                19.76,
                39.84,
                69.28,
                50.97,
                25.41,
                19.27,
                85.71,
                42.63);
        System.out.println(res5); // >>> OK

        List<Long> res6 = jedis.tdigestRank("racer_ages", 50);
        System.out.println(res6); // >>> [7]

        List<Long> res7 = jedis.tdigestRank("racer_ages", 50, 40);
        System.out.println(res7); // >>> [7, 4]

const res4 = await client.tDigest.create('racer_ages');
console.log(res4);  // >>> OK

const res5 = await client.tDigest.add('racer_ages', [
  45.88, 44.2, 58.03, 19.76, 39.84, 69.28, 50.97, 25.41, 19.27, 85.71, 42.63
]);
console.log(res5);  // >>> OK

const res6 = await client.tDigest.rank('racer_ages', [50]);
console.log(res6);  // >>> [7]

const res7 = await client.tDigest.rank('racer_ages', [50, 40]);
console.log(res7);  // >>> [7, 4]

double[] res8 = db.TDIGEST().Quantile("racer_ages", 0.5); ;
        Console.WriteLine(string.Join(", ", res8)); // >>> 44.2

        double[] res9 = db.TDIGEST().ByRank("racer_ages", 4);
        Console.WriteLine(string.Join(", ", res9)); // >>> 42.63

res8, err := rdb.TDigestQuantile(ctx, "racer_ages", 0.5).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res8) // >>> [44.2]

	res9, err := rdb.TDigestByRank(ctx, "racer_ages", 4).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res9) // >>> [42.63]

List<Double> res8 = jedis.tdigestQuantile("racer_ages", 0.5);
        System.out.println(res8); // >>> [44.2]

        List<Double> res9 = jedis.tdigestByRank("racer_ages", 4);
        System.out.println(res9); // >>> [42.63]

const res8 = await client.tDigest.quantile('racer_ages', [0.5]);
console.log(res8);  // >>> [44.2]

const res9 = await client.tDigest.byRank('racer_ages', [4]);
console.log(res9);  // >>> [42.63]

$res8 = $r->tdigestquantile('racer_ages', 0.5);
        echo json_encode($res8) . PHP_EOL;
        // >>> ["44.2"]

        $res9 = $r->tdigestbyrank('racer_ages', 4);
        echo json_encode($res9) . PHP_EOL;
        // >>> ["42.63"]

res8 = r.tdigest().quantile("racer_ages", 0.5)
print(res8)  # >>> [44.2]

res9 = r.tdigest().byrank("racer_ages", 4)
print(res9)  # >>> [42.63]

> TDIGEST.MIN racer_ages
"19.27"
> TDIGEST.MAX racer_ages
"85.709999999999994"

double res10 = db.TDIGEST().Min("racer_ages");
        Console.WriteLine(res10);   // >>> 19.27

        double res11 = db.TDIGEST().Max("racer_ages");
        Console.WriteLine(res11);   // >>> 85.71

res10, err := rdb.TDigestMin(ctx, "racer_ages").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res10) // >>> 19.27

	res11, err := rdb.TDigestMax(ctx, "racer_ages").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res11) // >>> 85.71

double res10 = jedis.tdigestMin("racer_ages");
        System.out.println(res10); // >>> 19.27

        double res11 = jedis.tdigestMax("racer_ages");
        System.out.println(res11); // >>> 85.71

const res10 = await client.tDigest.min('racer_ages');
console.log(res10);  // >>> 19.27

const res11 = await client.tDigest.max('racer_ages');
console.log(res11);  // >>> 85.71

$res10 = $r->tdigestmin('racer_ages');
        echo $res10 . PHP_EOL;
        // >>> 19.27

        $res11 = $r->tdigestmax('racer_ages');
        echo $res11 . PHP_EOL;
        // >>> 85.71

res10 = r.tdigest().min("racer_ages")
print(res10)  # >>> 19.27

res11 = r.tdigest().max("racer_ages")
print(res11)  # >>> 85.71

bool res12 = db.TDIGEST().Reset("racer_ages");
        Console.WriteLine(res12);   // >>> True

res12, err := rdb.TDigestReset(ctx, "racer_ages").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res12) // >>> OK

String res12 = jedis.tdigestReset("racer_ages");
        System.out.println(res12); // >>> OK

const res12 = await client.tDigest.reset('racer_ages');
console.log(res12);  // >>> OK

$res12 = $r->tdigestreset('racer_ages');
        echo $res12 . PHP_EOL;
        // >>> OK

res12 = r.tdigest().reset("racer_ages")
print(res12)  # >>> OK


Top-K

Top-K command summary

**7 commands in this group:**

[View all topk commands](https://redis.io/commands/?group=topk)

| Command | Summary | Complexity | Since |
|---------|---------|------------|-------|
| [TOPK.ADD](https://redis.io/commands/topk.add/) | Adds an item to a Top-k sketch. Multiple items can be added at the same time. | O(n * k) where n is the number of items and k i... | 2.0.0 |
| [TOPK.COUNT](https://redis.io/commands/topk.count/) | Return the count for one or more items are in a sketch | O(n) where n is the number of items | 2.0.0 |
| [TOPK.INCRBY](https://redis.io/commands/topk.incrby/) | Increases the count of one or more items by increment | O(n * k * incr) where n is the number of items,... | 2.0.0 |
| [TOPK.INFO](https://redis.io/commands/topk.info/) | Returns information about a sketch | O(1) | 2.0.0 |
| [TOPK.LIST](https://redis.io/commands/topk.list/) | Return the full list of items in Top-K sketch. | O(k*log(k)) where k is the value of top-k | 2.0.0 |
| [TOPK.QUERY](https://redis.io/commands/topk.query/) | Checks whether one or more items are in a sketch | O(n) where n is the number of items | 2.0.0 |
| [TOPK.RESERVE](https://redis.io/commands/topk.reserve/) | Initializes a Top-K sketch with specified parameters | O(1) | 2.0.0 |

Top K is a probabilistic data structure in Redis Open Source used to estimate the `K` highest-rank elements from a stream.

"Highest-rank" in this case means "elements with a highest number or score attached to them", where the score can be a count of how many times the element has appeared in the stream - thus making the data structure perfect for finding the elements with the highest frequency in a stream.
One very common application is detecting network anomalies and DDoS attacks where Top K can answer the question: Is there a sudden increase in the flux of requests to the same address or from the same IP?

There is, indeed, some overlap with the functionality of Count-Min Sketch, but the two data structures have their differences and should be applied for different use cases.

The Redis Open Source implementation of Top-K is based on the [HeavyKeepers](https://www.usenix.org/conference/atc18/presentation/gong) algorithm presented by Junzhi Gong et al. It discards some older approaches like "count-all" and "admit-all-count-some" in favour of a "**count-with-exponential-decay**" strategy which is biased against mouse (small) flows and has a limited impact on elephant (large) flows. This implementation uses two data structures in tandem: a hash table that holds the probabilistic counts (much like the Count-Min Sketch), and a min heap that holds the `K` items with the highest counts. This ensures high accuracy with shorter execution times than previous probabilistic algorithms allowed, while keeping memory utilization to a fraction of what is typically required by a Sorted Set. It has the additional benefit of being able to get real time notifications when elements are added or removed from the Top K list.

Use case

**Trending hashtags (social media platforms, news distribution networks)**

This application answers these questions:

- What are the K hashtags people have mentioned the most in the last X hours?
- What are the K news with highest read/view count today?

Data flow is the incoming social media posts from which you parse out the different hashtags.

The [`TOPK.LIST`]() command has a time complexity of `O(K*log(k))` so if `K` is small, there is no need to keep a separate set or sorted set of all the hashtags. You can query directly from the Top K itself.

Example

This example will show you how to track key words used "bike" when shopping online; e.g., "bike store" and "bike handlebars". Proceed as follows.

* Use [`TOPK.RESERVE`]() to initialize a top K sketch with specific parameters. Note: the `width`, `depth`, and `decay_constant` parameters can be omitted, as they will be set to the default values 7, 8, and 0.9, respectively, if not present.

 [code example]

 * Use [`TOPK.ADD`]() to add items to the sketch. As you can see, multiple items can be added at the same time. If an item is returned when adding additional items, it means that item was demoted out of the min heap of the top items, below it will mean the returned item is no longer in the top 5, otherwise `nil` is returned. This allows dynamic heavy-hitter detection of items being entered or expelled from top K list.

In the example below, "pedals" displaces "handlebars", which is returned after "pedals" is added. Also note that the addition of both "store" and "seat" a second time don't return anything, as they're already in the top K.

 * Use [`TOPK.LIST`]() to list the items entered thus far.

 * Use [`TOPK.QUERY`]() to see if an item is on the top K list. Just like [`TOPK.ADD`]() multiple items can be queried at the same time.
#### Code Examples

Top-K operations: Use TOPK.RESERVE to initialize a sketch, TOPK.ADD to track item frequencies, TOPK.LIST to retrieve top items, and TOPK.QUERY to check membership when you need to identify the most frequent items in a data stream

**Difficulty:** Intermediate

**Commands:** TOPK.RESERVE, TOPK.ADD, TOPK.LIST, TOPK.QUERY

**Complexity:**
- TOPK.RESERVE: O(1)
- TOPK.ADD: O(n * k)
- TOPK.LIST: O(k*log(k)
- TOPK.QUERY: O(n)

**Redis CLI:**

[code example]

**Available in:** Redis CLI, C# (Synchronous), Go, Java (Synchronous - Jedis), JavaScript (Node.js), PHP, Python

**C# (Synchronous):**

[code example]

**Go:**

[code example]

**Java (Synchronous - Jedis):**

[code example]

**JavaScript (Node.js):**

[code example]

**PHP:**

[code example]

**Python:**

[code example]

Sizing

Choosing the size for a Top K sketch is relatively easy, because the only two parameters you need to set are a direct function of the number of elements (K) you want to keep in your list.

If you start by knowing your desired `k` you can easily derive the width and depth:

[code example]

For the `decay_constant` you can use the value `0.9` which has been found as optimal in many cases, but you can experiment with different values and find what works best for your use case.

Performance

Insertion in a top-k has time complexity of O(K + depth) ≈ O(K) and lookup has time complexity of O(K), where K is the number of top elements to be kept in the list and depth is the number of hash functions used.

Academic sources

- [HeavyKeeper: An Accurate Algorithm for Finding Top-k Elephant Flows.](https://yangtonghome.github.io/uploads/HeavyKeeper_ToN.pdf)

References

- [Meet Top-K: an Awesome Probabilistic Addition to Redis](https://redis.com/blog/meet-top-k-awesome-probabilistic-addition-redis/)

> TOPK.RESERVE key k width depth decay_constant

> TOPK.RESERVE bikes:keywords 5 2000 7 0.925
OK
> TOPK.ADD bikes:keywords store seat handlebars handles pedals tires store seat
1) (nil)
2) (nil)
3) (nil)
4) (nil)
5) (nil)
6) handlebars
7) (nil)
8) (nil)
> TOPK.LIST bikes:keywords
1) store
2) seat
3) pedals
4) tires
5) handles
> TOPK.QUERY bikes:keywords store handlebars
1) (integer) 1
2) (integer) 0

bool res1 = db.TOPK().Reserve("bikes:keywords", 5, 2000, 7, 0.925);
        Console.WriteLine(res1);    // >>> True

        RedisResult[]? res2 = db.TOPK().Add("bikes:keywords",
                "store",
                "seat",
                "handlebars",
                "handles",
                "pedals",
                "tires",
                "store",
                "seat"
        );

        if (res2 is not null)
        {
            Console.WriteLine(string.Join(", ", string.Join(", ", res2.Select(r => $"{(r.IsNull ? "Null" : r)}"))));
            // >>> Null, Null, Null, Null, Null, handlebars, Null, Null
        }

        RedisResult[] res3 = db.TOPK().List("bikes:keywords");

        if (res3 is not null)
        {
            Console.WriteLine(string.Join(", ", string.Join(", ", res3.Select(r => $"{(r.IsNull ? "Null" : r)}"))));
            // >>> store, seat, pedals, tires, handles
        }

        bool[] res4 = db.TOPK().Query("bikes:keywords", "store", "handlebars");
        Console.WriteLine(string.Join(", ", res4)); // >>> True, False

res1, err := rdb.TopKReserve(ctx, "bikes:keywords", 5).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res1) // >>> OK

	res2, err := rdb.TopKAdd(ctx, "bikes:keywords",
		"store",
		"seat",
		"handlebars",
		"handles",
		"pedals",
		"tires",
		"store",
		"seat",
	).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res2) // >>> [     handlebars  ]

	res3, err := rdb.TopKList(ctx, "bikes:keywords").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res3) // [store seat pedals tires handles]

	res4, err := rdb.TopKQuery(ctx, "bikes:keywords", "store", "handlebars").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res4) // [true false]

String res1 = jedis.topkReserve("bikes:keywords", 5L, 2000L, 7L, 0.925D);
        System.out.println(res1); // >>> True

        List<String> res2 = jedis.topkAdd("bikes:keywords",
                "store",
                "seat",
                "handlebars",
                "handles",
                "pedals",
                "tires",
                "store",
                "seat");

        System.out.println(res2); // >>> [None, None, None, None, None, 'handlebars', None, None]

        List<String> res3 = jedis.topkList("bikes:keywords");
        System.out.println(res3); // >>> ['store', 'seat', 'pedals', 'tires', 'handles']

        List<Boolean> res4 = jedis.topkQuery("bikes:keywords", "store", "handlebars");
        System.out.println(res4); // >>> [1, 0]

const res1 = await client.topK.reserve('bikes:keywords', 5, {
    width: 2000,
    depth: 7,
    decay: 0.925
});
console.log(res1);  // >>> OK

const res2 = await client.topK.add('bikes:keywords', [
  'store',
  'seat',
  'handlebars',
  'handles',
  'pedals',
  'tires',
  'store',
  'seat'
]);
console.log(res2);  // >>> [null, null, null, null, null, 'handlebars', null, null]

const res3 = await client.topK.list('bikes:keywords');
console.log(res3);  // >>> ['store', 'seat', 'pedals', 'tires', 'handles']

const res4 = await client.topK.query('bikes:keywords', ['store', 'handlebars']);
console.log(res4);  // >>> [true, false]

$res1 = $r->topkreserve('bikes:keywords', 5, 2000, 7, 0.925);
        echo $res1 . PHP_EOL;
        // >>> OK

        $res2 = $r->topkadd(
            'bikes:keywords',
            'store',
            'seat',
            'handlebars',
            'handles',
            'pedals',
            'tires',
            'store',
            'seat',
        );
        echo json_encode($res2) . PHP_EOL;
        // >>> [null,null,null,null,null,"handlebars",null,null]

        $res3 = $r->topklist('bikes:keywords');
        echo json_encode($res3) . PHP_EOL;
        // >>> ["store","seat","pedals","tires","handles"]

        $res4 = $r->topkquery('bikes:keywords', 'store', 'handlebars');
        echo json_encode($res4) . PHP_EOL;
        // >>> [1,0]

"""
Code samples for Top-K pages:
    https://redis.io/docs/latest/develop/data-types/probabilistic/top-k/
"""

import redis

r = redis.Redis(decode_responses=True)

res1 = r.topk().reserve("bikes:keywords", 5, 2000, 7, 0.925)
print(res1)  # >>> True

res2 = r.topk().add(
    "bikes:keywords",
    "store",
    "seat",
    "handlebars",
    "handles",
    "pedals",
    "tires",
    "store",
    "seat",
)
print(res2)  # >>> [None, None, None, None, None, 'handlebars', None, None]

res3 = r.topk().list("bikes:keywords")
print(res3)  # >>> ['store', 'seat', 'pedals', 'tires', 'handles']

res4 = r.topk().query("bikes:keywords", "store", "handlebars")
print(res4)  # >>> [1, 0]

width = k*log(k)
depth =  log(k)  # but a minimum of 5