bloomfilter 以及count min sketch
2024-09-03 11:45:52
bloomfilter
http://blog.csdn.net/v_july_v/article/details/6685894
count min sketch
http://www.cnblogs.com/fxjwind/p/3289221.html
这个方法比较简单, 原理就是, 使用二维的hash table, w是hash table的取值空间, d是hash函数的个数
对某个element, 分别使用d个hash函数计算相应的hash值, 并在对应的bucket上递增1, 每个bucket的值称为sketch, 如图
然后在查询某个element的frequency时, 只需要取出所有d个sketch, 然后取最小的那个作为预估值, 如其名
因为为了节省空间, w*d是远小于真正的element个数的, 所以必然会出现很多的冲突, 而最小的那个应该是冲突最少的, 最精确的那个
这个方法的思路和bloom filter比较类似, 都是通过多个hash来降低冲突带来的影响
最新文章
- i++为什么没有自增探析——JVM中i++的实现(转)
- Python编程规范
- 关于Cococs中的CCActionEase
- [条款36]绝不重新定义继承而来的non-virtual函数
- 【开发技术】Eclipse插件Call Hierarchy简介及设置
- python celery任务分发
- 【新特性】JDK10
- webpack学习笔记--压缩代码
- Vue+element 实现文件导出xlsx格式
- Java引用类型转换
- maven添加settings.xml使用阿里云仓库
- nginx配置开机启动及配置sudo授权启动
- Ajax核心技术之XMLHttpRequest
- JAVA内存模型及垃圾回收自我总结
- pycharm 激活
- mysql数据安装问题汇总
- Nginx(三)：日志文件管理
- 1.1 Getting Started-Core Concepts
- __autoload 与spl_autoload_register()
- windows主机与virtualbox虚拟机下的Linux共享网络