首页 > 其他分享 >现有Sketch数据结构|持续更新|菜鸟学习

现有Sketch数据结构|持续更新|菜鸟学习

时间:2024-03-04 12:11:06浏览次数:27  
标签:Sketch hash 哈希 菜鸟 key 数据结构 函数

写在前面

比较简略,偏差之类的理论推导建议去读论文,如果有误麻烦指出

套话

Sketch的基础是概要数据结构(Summary Data Structure),它是一种可以以较小的内存消耗来表示和估计大规模数据集的某些属性的数据结构。

概要数据结构通过对原始数据进行压缩、聚合或采样,以及使用一些统计方法和算法来近似表示数据的特征和属性。概要数据结构通过对数据进行摘要(summary)的方式,能够在有限的存储空间下提供对原始数据的近似信息。

哈希函数在Sketch中起着关键的作用,它用于将输入数据映射到Sketch数据结构的存储空间中。哈希函数将输入数据转换为固定长度的哈希值,这个哈希值用于确定数据在Sketch中的位置或索引。

通过使用哈希函数,Sketch可以将大规模的数据集映射到有限的存储空间中,从而实现对数据的压缩和摘要。哈希函数具有均匀性和随机性的特点,可以将数据均匀地分布到Sketch的存储空间中,避免冲突和数据集中。

Count-min Sketch

image

共\(d\) 行每一行都对应一个hash函数\(h_{i}\) ,每一行都具有\(w\)个计数器\(c_{ij}\)

UPDATE:对于第\(i\) 行,\(C_{ih_{i}(key)}+=1\)

QUERY:对于一共d行 返回\(min(c_{ih_{i}(key)})\)

特点:会有假阳性,因为结果是不小于实际值的估计

Reference:CORMODE G, MUTHUKRISHNAN S. An Improved Data Stream Summary: The Count-Min Sketch and its Applications[J].

Count Sketch

结构和Count-min Sketch相似,但多了\(d\) 个hash函数,选择\(d\) 个hash函数\(h_{i}->[w]\) 以及\(s_{i}->\){1,-1},两者成对独立

UPDATE:\(C_{ih_{i}(key)}+=s_{i}(key)\)

QUERY:返回 \(median(s_{i}(key)C_{ih_{i}(key)})\)

特点:假阳性和假阴性都有可能,甚至会出现负数,\(s_{i}\) 的设计为了抵消一些冲突项

Reference:CHARIKAR M, CHEN K, FARACH-COLTON M. Finding frequent items in data streams[J/OL]. Theoretical Computer Science, 2004, 312(1): 3-15.

HyperLogLog

实例观察网站:http://content.research.neustar.biz/blog/hll.html

图片来源:HyperLogLog 算法的原理讲解以及 Redis 是如何应用它的 - 指尖下的幽灵 - 博客园 (cnblogs.com)
image

UPDATE:对数据流进行hash后得到的值,假设低\(p\) 位指示桶号,剩下的位从低到高第\(i\) 个数出现第一个1,且指示的桶号中数值小于\(i\) ,则更新

QUERY:对所有的桶中的值求调和平均,LogLog算法直接求平均,代入公式,其中\(const\) 是修正因子,\(m\) 是桶的数量
image
image

特点:适用于大流量的基数估计,小流量容易出现较大偏差

Reference:FLAJOLET P, FUSY É, GANDOUET O, 等. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm[J/OL]. Discrete Mathematics & Theoretical Computer Science, 2007, DMTCS Proceedings vol. AH,...(Proceedings): 3545.

标签:Sketch,hash,哈希,菜鸟,key,数据结构,函数
From: https://www.cnblogs.com/Dmmmy/p/17929456.html

相关文章

  • 现有Sketch数据结构|持续更新|菜鸟学习
    写在前面比较简略,偏差之类的理论推导建议去读论文,如果有误麻烦指出套话Sketch的基础是概要数据结构(SummaryDataStructure),它是一种可以以较小的内存消耗来表示和估计大规模数据集的某些属性的数据结构。概要数据结构通过对原始数据进行压缩、聚合或采样,以及使用一些统计方法......
  • 现有Sketch数据结构|持续更新|菜鸟学习
    现有Sketch数据结构基本原理写在前面比较简略,偏差之类的理论推导建议去读论文,如果有误麻烦指出套话由GPT生成Sketch的基础是概要数据结构(SummaryDataStructure),它是一种可以以较小的内存消耗来表示和估计大规模数据集的某些属性的数据结构。概要数据结构通过对原始数据进行......
  • 数据结构总纲
    一概述Java集合,也叫作容器,主要是由两大接口派生而来:一个是Collection接口,主要用于存放单一元素;另一个是Map接口,主要用于存放键值对。对于Collection接口,下面又有三个主要的子接口:List、Set和QueueJava集合框架如下图所示: ListArrayList:Object[]数组。Vector:O......
  • 探索数据结构:解锁计算世界的密码
    ✨✨欢迎大家来到贝蒂大讲堂✨✨......
  • 数据结构·基本概念
    DataStructureNotesAuthor:"ebxeax"Version:1.0RefreshDate2020.11.26Description:JustrecordandreviewsomepointsaboutDataStructure.Havemistakesthatpleasecorrectityourself.数据结构的基本概念1.数据2.数据元素:数据的基本单位,一个数据元......
  • 数据结构·查找算法
    查找1.顺序查找一般表(1)代码typedefstruct{ElemType*elem;inttableLen;}SSTable;intsearchSeq(SSTableST,ElemTypekey){ST.elem[e]=key;//设置哨兵for(inti=0;i<ST.tableLen;i++)returni;//存在返回,不存在返回1}(2)设......
  • 数据结构·线性表
    线性表一、逻辑结构和基本操作1.逻辑结构具有相同数据类型的n个数据元素的有限序列,表长n,n=0为空表表头:第一个元素表尾:最后一个元素除第一个元素外,每个元素有且仅有一个直接前驱除最后一个元素外,每个元素有且仅有一个直接后继2.基本操作initList(&L);len(L);locateE......
  • 数据结构之线性表(顺序存储表)
    php<?php/***CreatedbyPhpStorm.*User:SillyCat*Date:2024/3/2*Time:18:47*/classSequenceList{private$item=array();private$length=0;publicfunction__construct(){//$this->item=$item;......
  • 基础数据结构->set&&map
    set&&mapBEGIN:惜墨如金set用法#include<bits/stdc++.h>usingnamespacestd;voidthe_map(){map<string,int>ds;stringkis="kis";ds[kis]=2;ds["a+a"]=3;ds["b+"]=4;ds["c-"]=5;//这样就可将这个“数......
  • Redis基础数据结构
    简单动态字符串SDS在Redis里面字符串随处可见比如//设置一个(key,value)为msg和helloworld的键值对setmsg"helloworld"在这里,msg和helloworld都是一个字符串.Redis自己构建了一个名为SDS(SimpleDynamicString简单动态字符串)的类,用于作为Redis底层字符串的默认实......