Top-K

Top-K 是一种概率数据结构，允许您在数据流中找到最频繁的项目。

Top K 是 Redis Stack 中的一种概率数据结构，用于从流中估计 K 个最高排名的元素。

在这种情况下，“最高排名”意味着“具有最高数字或分数的元素”，其中分数可以是元素在流中出现的次数 - 从而使数据结构非常适合查找流中频率最高的元素。一个非常常见的应用是检测网络异常和DDoS攻击，其中Top K可以回答以下问题：是否有突然增加的请求流量到同一地址或来自同一IP？

确实，与Count-Min Sketch的功能有一些重叠，但这两个数据结构有其不同之处，应适用于不同的使用场景。

Redis Stack 的 Top-K 实现基于 Junzhi Gong 等人提出的 HeavyKeepers 算法。它摒弃了一些旧的方法，如“计数所有”和“允许所有计数部分”，转而采用“指数衰减计数”策略，该策略对小流量（鼠标流）有偏见，而对大流量（大象流）的影响有限。此实现同时使用了两种数据结构：一个保存概率计数的哈希表（类似于 Count-Min Sketch），以及一个保存计数最高的 K 个项的最小堆。这确保了比之前的概率算法更高的准确性和更短的执行时间，同时将内存利用率保持在通常有序集合所需的一小部分。它还有一个额外的好处，即当元素被添加到或从 Top K 列表中移除时，能够获得实时通知。

用例

热门话题标签（社交媒体平台，新闻分发网络）

这个应用程序回答以下问题：

在过去X小时内，人们提到最多的K个标签是什么？
今天阅读/观看次数最高的K条新闻是什么？

数据流是来自社交媒体的传入帖子，从中你可以解析出不同的标签。

TOPK.LIST 命令的时间复杂度为 O(K*log(k))，因此如果 K 很小，就没有必要维护一个单独的集合或排序集合来存储所有的标签。你可以直接从 Top K 本身进行查询。

Example

这个例子将向你展示如何在网上购物时跟踪使用的关键词“bike”；例如，“bike store”和“bike handlebars”。请按照以下步骤进行。

使用TOPK.RESERVE来初始化一个具有特定参数的top K草图。注意：width、depth和decay_constant参数可以省略，如果不存在，它们将分别设置为默认值7、8和0.9。

> TOPK.RESERVE key k width depth decay_constant

使用 TOPK.ADD 向草图添加项目。如你所见，可以同时添加多个项目。如果在添加额外项目时返回了一个项目，这意味着该项目被降级出前K项的最小堆，下面将意味着返回的项目不再在前5名中，否则返回 nil。这允许动态检测进入或退出前K列表的重击项目。在下面的示例中，“pedals”取代了“handlebars”，在添加“pedals”后返回“handlebars”。还要注意，第二次添加“store”和“seat”时没有返回任何内容，因为它们已经在前K中。
使用 TOPK.LIST 列出迄今为止输入的条目。

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.

>_ Redis CLI

> 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

Python

"""
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]

Node.js

import assert from 'assert';
import { createClient } from 'redis';

const client = createClient();
await client.connect();


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);  // >>> [1, 0]

Java-Sync

package io.redis.examples;


public class TopKExample {
    public void run(){
        UnifiedJedis unifiedJedis = new UnifiedJedis("redis://127.0.0.1:6379");


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

        List<String> res2 = unifiedJedis.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 = unifiedJedis.topkList("bikes:keywords");
        System.out.println(res3); // >>> ['store', 'seat', 'pedals', 'tires', 'handles']

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

package example_commands_test

import (
	"context"
	"fmt"

	"github.com/redis/go-redis/v9"
)


func ExampleClient_topk() {
	ctx := context.Background()

	rdb := redis.NewClient(&redis.Options{
		Addr:     "localhost:6379",
		Password: "", // no password docs
		DB:       0,  // use default DB
	})


	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]

}


using NRedisStack.RedisStackCommands;
using NRedisStack.Tests;
using StackExchange.Redis;



public class Topk_tutorial
{

    public void run()
    {
        var muxer = ConnectionMultiplexer.Connect("localhost:6379");
        var db = muxer.GetDatabase();


        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

        // Tests for 'topk' step.


    }
}

尺寸

选择Top K草图的大小相对容易，因为您需要设置的唯一两个参数是您希望在列表中保留的元素数量（K）的直接函数。

如果你从已知你想要的k开始，你可以很容易地推导出宽度和深度：

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

对于decay_constant，你可以使用值0.9，这在许多情况下已被发现为最优，但你可以尝试不同的值，找到最适合你用例的值。

性能

在top-k中插入的时间复杂度为O(K + depth) ≈ O(K)，查找的时间复杂度为O(K)，其中K是列表中保留的顶部元素的数量，depth是使用的哈希函数的数量。

学术资源

HeavyKeeper: 一种用于查找Top-k大象流的精确算法。

参考文献

Meet Top-K: RedisBloom 的一个令人惊叹的概率新增功能

Top-K

用例

Example

尺寸

性能

学术资源

参考文献

本页内容