{"id":807,"date":"2021-12-01T13:29:00","date_gmt":"2021-12-01T05:29:00","guid":{"rendered":"https:\/\/kylelv.com\/?p=807"},"modified":"2022-07-15T22:28:58","modified_gmt":"2022-07-15T14:28:58","slug":"%e9%83%a8%e5%88%86%e7%bd%91%e7%bb%9c%e6%b5%8b%e9%87%8f%e7%ae%97%e6%b3%95%ef%bc%88sketch%ef%bc%89%e5%a4%a7%e4%bd%93%e6%80%9d%e6%83%b3%e6%80%bb%e7%bb%93","status":"publish","type":"post","link":"https:\/\/blog.kylelv.com\/?p=807","title":{"rendered":"\u90e8\u5206\u7f51\u7edc\u6d4b\u91cf\u7b97\u6cd5\uff08sketch\uff09\u5927\u4f53\u601d\u60f3\u603b\u7ed3"},"content":{"rendered":"\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_73 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<label for=\"ez-toc-cssicon-toggle-item-69fddf0b1b3c8\" class=\"ez-toc-cssicon-toggle-label\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-69fddf0b1b3c8\"  aria-label=\"Toggle\" \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/blog.kylelv.com\/?p=807\/#%E5%9F%BA%E6%95%B0%E4%BC%B0%E8%AE%A1%E7%AE%97%E6%B3%95\" title=\"\u57fa\u6570\u4f30\u8ba1\u7b97\u6cd5\">\u57fa\u6570\u4f30\u8ba1\u7b97\u6cd5<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/blog.kylelv.com\/?p=807\/#Linear_Counting\" title=\"Linear Counting\">Linear Counting<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/blog.kylelv.com\/?p=807\/#FM_Sketch%EF%BC%88PCSA%EF%BC%89\" title=\"FM Sketch\uff08PCSA\uff09\">FM Sketch\uff08PCSA\uff09<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/blog.kylelv.com\/?p=807\/#LogLog\" title=\"LogLog\">LogLog<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/blog.kylelv.com\/?p=807\/#Kmin\" title=\"Kmin\">Kmin<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/blog.kylelv.com\/?p=807\/#Misra-Gries\" title=\"Misra-Gries\">Misra-Gries<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/blog.kylelv.com\/?p=807\/#Bloom_Filter\" title=\"Bloom Filter\">Bloom Filter<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/blog.kylelv.com\/?p=807\/#Counting_Bloom_Filter\" title=\"Counting Bloom Filter\">Counting Bloom Filter<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/blog.kylelv.com\/?p=807\/#CM_Sketch\" title=\"CM Sketch\">CM Sketch<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-10\" href=\"https:\/\/blog.kylelv.com\/?p=807\/#Count_Sketch\" title=\"Count Sketch\">Count Sketch<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-11\" href=\"https:\/\/blog.kylelv.com\/?p=807\/#CU_Sketch\" title=\"CU Sketch\">CU Sketch<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-12\" href=\"https:\/\/blog.kylelv.com\/?p=807\/#LD_Sketch\" title=\"LD Sketch\">LD Sketch<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-13\" href=\"https:\/\/blog.kylelv.com\/?p=807\/#MV_Sketch\" title=\"MV Sketch\">MV Sketch<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-14\" href=\"https:\/\/blog.kylelv.com\/?p=807\/#FlowRadar\" title=\"FlowRadar\">FlowRadar<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-15\" href=\"https:\/\/blog.kylelv.com\/?p=807\/#UnivMon\" title=\"UnivMon\">UnivMon<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-16\" href=\"https:\/\/blog.kylelv.com\/?p=807\/#ElasticSketch\" title=\"ElasticSketch\">ElasticSketch<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E5%9F%BA%E6%95%B0%E4%BC%B0%E8%AE%A1%E7%AE%97%E6%B3%95\"><\/span>\u57fa\u6570\u4f30\u8ba1\u7b97\u6cd5<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Linear_Counting\"><\/span><strong>Linear Counting<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>\u8be5\u7b97\u6cd5\u7528\u4e8e\u4f30\u6d4b\u6570\u636e\u57fa\u6570\uff0c\u4e5f\u5c31\u662f\u8bf4\u6709\u591a\u5c11\u4e0d\u540c\u5143\u7d20\uff0c\u91c7\u7528\u65b9\u6cd5\u975e\u5e38\u7b80\u5355\uff0c\u5c06\u6570\u636e\u54c8\u5e0c\u5230\u957f\u5ea6\u4e3am\u7684\u6570\u7ec4\uff0c\u8bbf\u95ee\u5230\u7684\u4f4d\u7f6e\u5c31\u7f6e\u4e3a1<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" src=\"http:\/\/blog.codinglabs.org\/uploads\/pictures\/algorithms-for-cardinality-estimation-part-ii\/1.png\" alt=\"Linear Counting\"\/><\/figure><\/div>\n\n\n<p>\u6211\u4eec\u53ef\u4ee5\u8fd1\u4f3c\u8ba4\u4e3a\u54c8\u5e0c\u7684\u7ed3\u679c\u670d\u4ece\u5747\u5300\u5206\u5e03\uff0c\u90a3\u4e48\u6700\u540e\u8bbe\u96c6\u5408\u57fa\u6570\u4e3an\u7684\u6700\u5927\u4f3c\u7136\u4f30\u8ba1\u4e3a\\(\u2212m\\cdot ln(\\frac{u}{m}) \\)\uff0c\u5176\u4e2du\u4e3a\u54c8\u5e0c\u8868\u4e2d0\u7684\u4e2a\u6570<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>\u8bba\u6587\uff1a- Whang, Kyu-Young, Brad T. Vander-Zanden, and Howard M. Taylor. &#8220;A linear-time probabilistic counting algorithm for database applications.&#8221; ACM Transactions on Database Systems (TODS) 15.2 (1990): 208-229.<\/p><\/blockquote>\n<\/div><\/div>\n\n\n\n<p><\/p>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"FM_Sketch%EF%BC%88PCSA%EF%BC%89\"><\/span><strong>FM Sketch<\/strong>\uff08PCSA\uff09<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>\u8be5\u7b97\u6cd5\u662f<meta charset=\"utf-8\">\u57fa\u4e8e\u6982\u7387\u6765\u4f30\u8ba1\u57fa\u6570\uff0c\u9996\u5148\u6211\u4eec\u6839\u636e\u6570\u636e\u968f\u673a\u60c5\u51b5\u89c2\u5bdf\u4e8c\u8fdb\u5236\u7684\u6027\u8d28\uff0c\u53ef\u4ee5\u53d1\u73b0\u672b\u5c3e\u6709\\(k\\)\u4e2a\u8fde\u7eed0\u7684\u60c5\u51b5\u51fa\u73b0\u6b21\u6570\u662f\u6309\u6bd4\u4f8b\u7f29\u5c0f\u7684\uff0c\u56e0\u6b64\u6211\u4eec\u57fa\u4e8e\u8fd9\u4e2a\u89c2\u5bdf\u5f97\u51fa\u4f30\u8ba1\u65b9\u6cd5<\/p>\n\n\n\n<p>\u9996\u5148\u6211\u4eec\u968f\u673a\u4e00\u4e2a\u54c8\u5e0c\u51fd\u6570\u5c06\u6570\u636e\u6620\u5c04\u5230\u4e00\u4e2a\u4e8c\u8fdb\u5236\u957f\u5ea6\u4e3a\\(L\\)\u7684\u7a7a\u95f4\u5185\uff08\u5373\\([0,2^L-1]\\) \uff09\uff0c\u6211\u4eec\u8bb0\u5f55BITMAP\u6765\u6807\u8bb0\u662f\u5426\u51fa\u73b0\u4e00\u4e2a\u6570\u540e\u5c3e\u6070\u597d\u6709\u8fde\u7eed\\(i\\)\u4e2a0\uff0c\u8fd9\u6837\u663e\u7136\u6839\u636e\u8bbf\u95ee\u7684\u6982\u7387\u5c31\u53ef\u4ee5\u4f30\u8ba1\u6570\u636e\u57fa\u6570\uff0c\u6211\u4eec\u53d6\u5728bitmap\u4e2d\u7b2c\u4e00\u4e2a\u4e3a0\u7684\u4f4d\u7f6e\uff0c\u5373\u6211\u4eec\u6ca1\u6709\u6620\u5c04\u540e\u672b\u5c3e\u6070\u597d\u6709\\(k\\)\u4e2a0\u7684key\uff0c\u56e0\u6b64\u6211\u4eec\u7528\\(k\\)\u6765\u8fd1\u4f3c\\(\\log n \\)\uff0c\u663e\u7136\u8fd9\u6837\u6570\u636e\u662f\u504f\u5c0f\u7684\uff0c\u8bba\u6587\u6839\u636e\u8ba1\u7b97\u6dfb\u52a0\u4e86\u504f\u5dee\u53c2\u6570\\(E(k)=\\log\\phi n,\\phi=0.77351\\cdots\\)<\/p>\n\n\n\n<p>\u663e\u7136\u8fd9\u6837\u8fd8\u662f\u4e0d\u592a\u51c6\u786e\uff0c\u4e8e\u662f\u5c31\u91c7\u7528\u4e86\u591a\u6b21\u54c8\u5e0c\u7684\u65b9\u5f0f\uff0c\u6211\u4eec\u5229\u7528\u5f97\u5230\u7684\\(k\\)\u7684\u5747\u503c\u6765\u8fdb\u884c\u4f30\u8ba1<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>\u8bba\u6587\uff1aFlajolet, Philippe, and G. Nigel Martin. &#8220;Probabilistic counting algorithms for data base applications.&#8221;&nbsp;<em>Journal of computer and system sciences<\/em>&nbsp;31.2 (1985): 182-209.<\/p><\/blockquote>\n\n\n\n<p><\/p>\n<\/div><\/div>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"LogLog\"><\/span><strong>LogLog<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>\u987e\u540d\u601d\u4e49\uff0c\u5c31\u662f\u5229\u7528loglogn\u7684\u7a7a\u95f4\u6765\u5b9e\u73b0\u4f30\u6d4b\u57fa\u6570\u7684\u7b97\u6cd5\u3002\u53ef\u4ee5\u8bf4\u57fa\u672c\u5c31\u662fFM\u7684\u4f18\u5316\uff0c\u6211\u4eec\u8bb0\u5f55\\(p(x)\\)\u8868\u793a\u5bf9\u4e8e\u60f3\u54c8\u5e0c\u4e4b\u540e\u672b\u5c3e\u6709\\(p(x)\\)\u4e2a0\uff0c\u90a3\u4e48\u5176\u5b9e\u6211\u4eec\u53ea\u9700\u8981\u8bb0\u5f55\\(max(p(x))\\)\u5373\u53ef\uff0c\u56e0\u6b64\u8be5\u7a7a\u95f4\u4e3aloglogn\u7684<\/p>\n\n\n\n<p><meta charset=\"utf-8\">\u90a3\u4e48\u540c\u6837\uff0c\u6211\u4eec\u53ef\u4ee5\u91c7\u7528\u5c06\u6570\u636e\u968f\u673a\u5206\u6876\u7edf\u8ba1\uff0c\u901a\u8fc7\u6c42max\u7684\u5e73\u5747\u503c\u6765\u4f30\u6d4b<\/p>\n\n\n\n<p>HyperLogLog\u7b97\u6cd5\u4f7f\u7528\u8c03\u548c\u5e73\u5747\u503c\u5c06\u5b83\u4eec\u7ec4\u5408\u6210\u539f\u59cb\u57fa\u6570\u7684\u4f30\u8ba1\u503c<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>\u53c2\u8003\uff1a<a href=\"https:\/\/zhuanlan.zhihu.com\/p\/271186546\" target=\"_blank\" rel=\"noreferrer noopener\">https:\/\/zhuanlan.zhihu.com\/p\/271186546<\/a><\/p><cite>\u57fa\u6570\u4f30\u8ba1\u7b97\u6cd5\uff08\u5305\u62ecHLL\u3001AC\uff09<\/cite><\/blockquote>\n<\/div><\/div>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Kmin\"><\/span><strong>Kmin<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>KMV Sketch\u662f\u7528\u4e8e\u7edf\u8ba1\u6570\u636e\u6d41\u4e2d\u4e0d\u540c\u5143\u7d20\u4e2a\u6570\uff0c\u663e\u7136\u76f4\u63a5\u7edf\u8ba1\u7a7a\u95f4\u5f00\u9500\u662fO(n)\u7684\uff0c\u8be5\u7b97\u6cd5\u5229\u7528\u4e86\u968f\u673a\u54c8\u5e0c\u7684\u6027\u8d28\u6765\u8fd1\u4f3c\u7684\u4f30\u8ba1<\/p>\n\n\n\n<p>\u9996\u5148\uff0c\u6211\u4eec\u5047\u8bbe\u5b58\u5728\u4e00\u4e2a\u975e\u5e38\u4f18\u7f8e\u7684\u54c8\u5e0c\uff0c\u4ed6\u5c06\u6570\u636e\u5747\u5300\u7684\u5206\u5e03\u5728\u4e86[0,1]\u7684\u533a\u95f4\u5185\uff0c\u8fd9\u6837\u6211\u4eec\u53d1\u73b0\u6211\u4eec\u53ea\u9700\u8981\u8003\u8651\u79bb0\u6700\u8fd1\u7684\u70b9\u7684\u8ddd\u79bb\uff0c\u5c31\u53ef\u4ee5\u4f30\u6d4b\u5177\u4f53\u6709\u591a\u5c11\u4e2a\u503c\u88ab\u54c8\u5e0c\u8fdb\u6765\uff0c\u5373\uff081\/\u6700\u8fd1\u8ddd\u79bb\uff09<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" src=\"https:\/\/agkn.files.wordpress.com\/2012\/06\/kmv_fig1b5.png?w=549&amp;h=133\" alt=\"\"\/><\/figure><\/div>\n\n\n<p>\u4f46\u662f\u8fd9\u6837\u663e\u7136\u4f1a\u6709\u8f83\u5927\u7684\u8bef\u5dee\uff0c\u56e0\u6b64\u6211\u4eec\u91c7\u7528\u524dk\u5c0f\u7684\u70b9\u6765\u4f30\u6d4b\uff0c\u90a3\u4e48\u6700\u540e\u6211\u4eec\u53d6(k-1)\/max(KMV)\u4e3a\u7b54\u6848<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" src=\"https:\/\/agkn.files.wordpress.com\/2012\/06\/kmv_fig1c3.png?w=544&amp;h=106\" alt=\"\"\/><\/figure><\/div>\n\n\n<p>\u8fd9\u91cc\u7684\u201c-1\u201d\u4fee\u6b63\u7684\u5177\u4f53\u63a8\u5bfc\u53ef\u4ee5\u53c2\u89c1\u8bba\u6587<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>\u53c2\u8003\uff1a<a href=\"https:\/\/agkn.wordpress.com\/2012\/07\/09\/sketch-of-the-day-k-minimum-values\/\" target=\"_blank\" rel=\"noreferrer noopener\">https:\/\/agkn.wordpress.com\/2012\/07\/09\/sketch-of-the-day-k-minimum-values\/<\/a><\/p><\/blockquote>\n<\/div><\/div>\n\n\n\n<p><\/p>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Misra-Gries\"><\/span><strong>Misra-Gries<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u8be5\u7b97\u6cd5\u7528\u4e8e\u67e5\u627e\u9891\u7e41\u9879\uff0c\u6211\u4eec\u57fa\u4e8e\u7ed9\u5b9a\u9891\u7387\uff0c\u4ee5\u4e00\u5b9a\u8bef\u5dee\u4e3a\u4ee3\u4ef7\u6765\u8282\u7ea6\u7a7a\u95f4\uff0c\u8fd1\u4f3c\u627e\u5230\u6240\u6709\u51fa\u73b0\u6b21\u6570\u5927\u4e8e\u8be5\u9891\u7387\u7684\u9879<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"http:\/\/i.imgur.com\/AaKXhv6.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<p>\u8003\u8651\u548c\u627e\u6982\u7387\u8d85\u8fc7\u4e00\u534a\u5143\u7d20\u7684\u601d\u60f3\u7c7b\u4f3c\uff0c\u6211\u4eec\u7ef4\u62a4k\u4e2a\u6876\uff0c\u5148\u586b\u6ee1\u4e4b\u540e\u672b\u5c3e\u6dd8\u6c70\uff0c\u65b0\u6765\u7684\u9879\u5982\u679c\u4e0d\u5728\u91cc\u9762\u6211\u4eec\u5373\u53ef\u80fd\u5e94\u8be5\u820d\u5f03\uff0c\u8fd9\u65f6\u6211\u4eec\u5373\u5b9e\u9645\u4e0a\u5c11\u8bb0\u5f55\u4e86\u4e00\u6b21\uff0c\u90a3\u4e48\u6211\u4eec\u5c06\u6876\u5185\u7684\u6240\u6709count-1\uff0c\u6765\u4fdd\u8bc1\u76f8\u5bf9\u7a33\u5b9a<\/p>\n\n\n\n<p>\u8fd9\u6837\u5728\u6876\u5185\u7684\u5927\u6982\u7387\u4e3a\u9891\u7e41\u9879\uff0c\u4f46\u662f\u9891\u7e41\u9879\u4e00\u5b9a\u5728\u6876\u4e2d<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>\u53c2\u8003\uff1a<a href=\"https:\/\/en.wikipedia.org\/wiki\/Misra%E2%80%93Gries_summary\" target=\"_blank\" rel=\"noreferrer noopener\">https:\/\/en.wikipedia.org\/wiki\/Misra%E2%80%93Gries_summary<\/a><\/p><\/blockquote>\n<\/div><\/div>\n\n\n\n<p><\/p>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Bloom_Filter\"><\/span><strong>Bloom Filter<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u5e03\u9686\u8fc7\u6ee4\u5668\u7528\u4e8e\u8fd1\u4f3c\u627e\u5230\u4e00\u4e2a\u5143\u7d20\u662f\u5426\u5728\u7ed9\u5b9a\u96c6\u5408\u5185\u51fa\u73b0\uff0c\u5373\u5b9e\u73b0\u7c97\u201c\u8fc7\u6ee4\u201d\u64cd\u4f5c\u3002<\/p>\n\n\n\n<p>\u540c\u6837\u91c7\u53d6\u54c8\u5e0c\u7684\u65b9\u5f0f\uff0c\u6211\u4eec\u4e3a\u4e86\u51cf\u5c0f\u54c8\u5e0c\u51b2\u7a81\uff0c\u5c06\u4e00\u4e2a\u5143\u7d20\u54c8\u5e0c\u5230\u4e0d\u540c\u4f4d\u7f6e\uff0c\u90a3\u4e48\u6211\u4eec\u8ba4\u4e3a\u8fd9\u4e9b\u4f4d\u7f6e\u5168\u90e8\u88ab\u7f6e1\u624d\u4e3a\u96c6\u5408\u5185\u5143\u7d20<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/kylelv.com\/wp-content\/uploads\/2021\/07\/1030776-20170106143141784-1475031003.jpg\" alt=\"\" class=\"wp-image-814\" width=\"572\" height=\"206\" srcset=\"https:\/\/blog.kylelv.com\/wp-content\/uploads\/2021\/07\/1030776-20170106143141784-1475031003.jpg 952w, https:\/\/blog.kylelv.com\/wp-content\/uploads\/2021\/07\/1030776-20170106143141784-1475031003-300x108.jpg 300w, https:\/\/blog.kylelv.com\/wp-content\/uploads\/2021\/07\/1030776-20170106143141784-1475031003-768x278.jpg 768w\" sizes=\"auto, (max-width: 572px) 100vw, 572px\" \/><\/figure><\/div>\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>\u8bba\u6587\uff1aBloom, Burton H. &#8220;Space\/time trade-offs in hash coding with allowable errors.&#8221; Communications of the ACM 13.7 (1970): 422-426.<\/p><\/blockquote>\n<\/div><\/div>\n\n\n\n<p><\/p>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Counting_Bloom_Filter\"><\/span><strong>Counting Bloom Filter<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u6211\u4eec\u53d1\u73b0bloomfilter\u5bf9\u4e8e\u9759\u6001\u96c6\u5408\u6709\u8f83\u4f18\u7684\u6027\u80fd\uff0c\u4f46\u662f\u6211\u4eec\u65e0\u6cd5\u5728\u96c6\u5408\u4e2d\u8fdb\u884c\u5220\u9664\u5143\u7d20\uff0c\u56e0\u4e3a\u6211\u4eec\u5e76\u4e0d\u77e5\u9053\u5220\u9664\u4e4b\u540e\u662f\u5426\u5c06\u5bf9\u5e94\u4f4d\u7f6e0<\/p>\n\n\n\n<p>\u56e0\u6b64\u6211\u4eec\u5f15\u5165\u4e86\u8ba1\u6570\u5668\uff0c\u5c06\u4e4b\u524d\u7684\u8d4b\u503c\u53d8\u6210\u4e86+1\uff0c\u8fd9\u6837\u6211\u4eec\u5220\u9664\u7684\u65f6\u5019\u5728\u5bf9\u5e94\u4f4d\u7f6e-1\u5373\u53ef<\/p>\n<\/div><\/div>\n\n\n\n<p><\/p>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"CM_Sketch\"><\/span><strong>CM Sketch<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>count min sketch\u5229\u7528\u591a\u4e2a\u54c8\u5e0c\u51fd\u6570\uff0c\u5c06\u6570\u636e\u6d41\u8fdb\u884c\u54c8\u5e0c\uff0c\u4e5f\u5c31\u662f\u8bf4\u5185\u90e8\u7ed3\u6784\u4e3a\u4e00\u4e2ah*w\u7684\u6570\u7ec4\u8868\u793ah\u4e2a\u4f4d\u7f6e\uff0c\u7528w\u4e2a\u54c8\u5e0c\u51fd\u6570<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/pic1.zhimg.com\/80\/v2-84c85f26e06f22c94f3ed7f01da9e978_1440w.jpg\" alt=\"CM Sketch\" width=\"522\" height=\"193\"\/><\/figure><\/div>\n\n\n<p>\u6211\u4eec\u6bcf\u6b21\u66f4\u65b0\u5373\u5728\u6bcf\u4e2a\u54c8\u5e0c\u5bf9\u5e94\u4f4d\u7f6e\u52a0\u4e0a\u5f53\u524d\u7684size<br>\u6b64\u65f6\u6211\u4eec\u53d1\u73b0\u7531\u4e8e\u5b58\u5728\u54c8\u5e0c\u51b2\u7a81\u6bcf\u4e2a\u4f4d\u7f6e\u5bf9\u5e94\u503c\u5fc5\u7136\u4f1a\u53d7\u5230\u5176\u4ed6\u7684\u5f71\u54cd\u800c\u53d8\u5927<br>\u56e0\u6b64\u6211\u4eec\u53d6\u8fd9w\u4e2a\u7684\u6700\u5c0f\u503c\u4f5c\u4e3a\u6211\u4eec\u7684\u9884\u4f30\u503c<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>\u8bba\u6587\uff1aCormode, Graham, and Shan Muthukrishnan. &#8220;An improved data stream summary: the count-min sketch and its applications.&#8221; Journal of Algorithms 55.1 (2005): 58-75.<\/p><\/blockquote>\n<\/div><\/div>\n\n\n\n<p><\/p>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Count_Sketch\"><\/span><strong>Count Sketch<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u8003\u8651\u5bf9\u4e8e\u6bcf\u4e2a\u6876\u4f1a\u6709\u5176\u4ed6\u5143\u7d20\u7684\u54c8\u5e0c\u51b2\u7a81\u5bfc\u81f4\u8ba1\u6570\u504f\u5927\uff0c\u6211\u4eec\u60f3\u5c3d\u53ef\u80fd\u51cf\u5c11\u5176\u5f71\u54cd<br>\u8fd9\u91cc\u6211\u4eec\u540c\u6837\u91c7\u7528\u4e00\u4e2a\u54c8\u5e0c\u51fd\u6570h\u6620\u5c04\u5230w\u4e2a\u6876\u4e2d\uff0c\u4e4b\u540e\u6211\u4eec\u65b0\u968f\u673a\u4e00\u4e2a\u54c8\u5e0c\u51fd\u6570g\u5c06n\u4e2a\u503c\u968f\u673a\u6620\u5c04\u4e3a{-1,1}<br>\u8fd9\u6837\u6211\u4eec\u5c06\u52a0\u6cd5\u8ba1\u6570\u64cd\u4f5c\u53d8\u4e3a\\( C[h(i)]+=c\\cdot g(i) \\)\uff0c\u8fd9\u6837\u6211\u4eec\u57fa\u4e8e\u968f\u673a\u7684\u65b9\u5f0f\uff0c\u8003\u8651\u5176\u4ed6\u5bf9\u8be5\u4f4d\u7f6e\u5f71\u54cd\u7684\u5143\u7d20\u662f\u968f\u673a\u8fdb\u884c\u52a0\u51cf\u8bb0\u5f55\u7684\uff0c\u56e0\u6b64\u51cf\u5c0f\u4e86\u5176\u5f71\u54cd<br>\u8fd9\u6837\u6211\u4eec\u67e5\u8be2\u64cd\u4f5c\u5c31\u53d8\u6210\u4e86\u8fd4\u56de\\(g(i)\\cdot C[h(i)] \\)<\/p>\n\n\n\n<p>\u5f53\u7136\u8fd9\u6837\u7684\u64cd\u4f5c\u4ecd\u5b58\u5728\u5f88\u5927\u7684\u968f\u673a\u504f\u5dee\uff0c\u56e0\u6b64\u6211\u4eec\u91c7\u7528\u591a\u4e2a\u54c8\u5e0c\u51fd\u6570\uff0c\u5373\u8bb0\u5f55\u4e0e\u8ba1\u7b97\u591a\u6b21\uff0c\u5bf9\u4e8e\u67e5\u8be2\u64cd\u4f5c\u53d6\u5bf9\u4e8e\u6bcf\u7ec4\u54c8\u5e0c\u7684\u5bf9\u5e94\u67e5\u8be2\u7684\u5747\u503c<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>\u8bba\u6587\uff1aM. Charikar, K. Chen, and M. Farach-Colton. Finding frequent items in data streams. Automata, languages and programming, pages 784\u2013784, 2002.<\/p><\/blockquote>\n<\/div><\/div>\n\n\n\n<p><\/p>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"CU_Sketch\"><\/span><strong>CU Sketch<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>CU Sketch \u53ea\u662f\u5bf9\u4e8eCM \u8fdb\u884c\u4e86\u5fae\u5c0f\u7684\u6539\u52a8\uff0c\u5373\u53d8\u6210\u4e86\u201c\u4fdd\u5b88\u66f4\u65b0\u201d\u3002\u5728\u66f4\u65b0\u7684\u65f6\u5019\uff0c\u628a\u4e4b\u524d\u5bf9\u4e8e\u6bcf\u4e2acounter\u8fdb\u884c\u52a0\u6cd5\u7684\u64cd\u4f5c\u53d8\u6210\u4e86\u53ea\u5bf9\u4e8e\u6700\u5c0f\u7684counter\u505a+1\uff0c\u8fd9\u6837\u663e\u7136\u6b63\u786e\u6027\u8fd8\u53ef\u4ee5\u4fdd\u8bc1\uff0c\u5e76\u4e14\u5927\u5e45\u63d0\u5347\u4e86\u51c6\u786e\u5ea6\uff0c\u4f46\u663e\u7136\u5c31\u5931\u53bb\u4e86\u5bf9\u4e8e\u5220\u9664\u64cd\u4f5c\u7684\u652f\u6301\u3002<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>\u8bba\u6587\uff1a- C. Estan and G. Varghese. New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice. ACM Transactions on Computer Systems (TOCS), 21(3):270\u2013313, 2003.<\/p><\/blockquote>\n\n\n\n<p><\/p>\n<\/div><\/div>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"LD_Sketch\"><\/span><strong>LD Sketch<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u7b97\u6cd5\u7528\u4e8e\u68c0\u6d4bheavy hitter\u548cheavy changer\uff0c\u57fa\u4e8e\u4e86\u5206\u5e03\u5f0f\u7cfb\u7edf\u8bbe\u8ba1\u4e86\u7b97\u6cd5\uff0c\u5e76\u4e14\u5229\u7528\u5f39\u6027\u6570\u7ec4\u6765\u8282\u7ea6\u5185\u5b58\u4f7f\u7528\u3002<\/p>\n\n\n\n<p>\u540c\u6837\u91c7\u7528\u4e86\u591a\u4e2a\u54c8\u5e0c\u51fd\u6570\u7684\u65b9\u5f0f\uff0c\u548c\u6734\u7d20\u7684\u76f8\u6bd4\uff0c\u5bf9\u4e8e\u6bcf\u4e2a\u4f4d\u7f6e\u591a\u7ef4\u62a4\u4e86\u5f39\u6027\u6570\u7ec4A\u8bb0\u5f55\u5177\u4f53\u4fe1\u606f\u4ee5\u53ca\u5176\u5927\u5c0fl\uff08\u6307\u50a8\u5b58\u7684\u4e0d\u540c\u952e\u503c\u4e2a\u6570\uff09\u548c\u6876\u5185\u952e\u503c\u7684\u6700\u5927\u4f30\u8ba1\u8bef\u5deee<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/kylelv.com\/wp-content\/uploads\/2021\/08\/image-1024x653.png\" alt=\"\" class=\"wp-image-835\" width=\"453\" height=\"288\" srcset=\"https:\/\/blog.kylelv.com\/wp-content\/uploads\/2021\/08\/image-1024x653.png 1024w, https:\/\/blog.kylelv.com\/wp-content\/uploads\/2021\/08\/image-300x191.png 300w, https:\/\/blog.kylelv.com\/wp-content\/uploads\/2021\/08\/image-768x489.png 768w, https:\/\/blog.kylelv.com\/wp-content\/uploads\/2021\/08\/image.png 1224w\" sizes=\"auto, (max-width: 453px) 100vw, 453px\" \/><\/figure><\/div>\n\n\n<p>\u8fd9\u91ccl\u7684\u5927\u5c0f\u6211\u4eec\u6876\u7684\u603bval\u548c\u8bbe\u5b9a\u9600\u503c\u6bd4\u503c\u800c\u5f39\u6027\u53d8\u6362\uff08\u5177\u4f53\u53ef\u53c2\u8003\u8bba\u6587\uff09\uff0c\u90a3\u4e48\u6570\u7ec4A\u4e2d\u4fe1\u606f\u66f4\u65b0\u53c2\u7167\u4e0a\u9762<meta charset=\"utf-8\">Misra-Gries\u7b97\u6cd5\u800c\u8fdb\u884c\u672b\u5c3e\u6dd8\u6c70\uff0c\u4ece\u800c\u7ef4\u62a4\u9891\u7e41\u9879\u7684\u8f83\u5177\u4f53\u4fe1\u606f\uff0c\u5e76\u4e14\u6211\u4eec\u7ef4\u62a4e\u7684\u4fe1\u606f\u5373\u7d2f\u8ba1\u5728<meta charset=\"utf-8\">Misra-Gries\u7b97\u6cd5\u5b9e\u73b0\u4e2d\u6570\u7ec4\u6574\u4f53\u51cf\u5c0f\u7684\u603b\u503c<\/p>\n\n\n\n<p>\u90a3\u5bf9\u5e94heavy hitter\u68c0\u6d4b\u5c31\u53d8\u6210\u5bf9\u4e8e\u6bcf\u4e2a\u54c8\u5e0c\u51fd\u6570\u67e5\u8be2\u5bf9\u5e94\u4f30\u503c\u7684\u4e0a\u754c\uff0c\u5982\u679c\u90fd\u5927\u4e8e\u8bbe\u5b9a\u9600\u503c\u5219\u5224\u65ad\u4e3a\u6b63<\/p>\n\n\n\n<p><strong>\u5206\u5e03\u5f0f\u68c0\u6d4b<\/strong>\uff1a\u9996\u5148\u5c06\u6570\u636e\u901a\u8fc7\u54c8\u5e0c\u968f\u673a\u5230\u4e00\u4e2a\u5927\u5c0f\u4e3a\\(d\\)\u7684worker\u96c6\u5408\u4e2d\uff0c\u663e\u7136\u5bf9\u4e8e\u540c\u4e00\u952e\u503c\u5fc5\u7136\u59cb\u7ec8\u5728\u4e00\u4e2a\u96c6\u5408\uff0c\u7136\u540e\u8ba9\u8fdc\u7a0b\u7ad9\u70b9\u9009\u62e9\u4e00\u4e2aworker\u8fdb\u884c\u53d1\u9001\u6570\u636e\uff0c\u8fd9\u6837\u6bcf\u4e2a\u7ad9\u70b9\u5e73\u5747\u6536\u5230\u4e86\\(1\/d\\)\uff0c\u6211\u4eec\u4fee\u6539\u4e00\u4e0b\u9600\u503c\uff08\u5e76\u6dfb\u52a0\u4e86\u4e00\u4e2a\u4fee\u6b63\u53c2\u6570\uff1f\uff09\uff0c\u90a3\u4e48\u6211\u4eec\u5bf9\u4e8ehh\u7684\u68c0\u6d4b\u5c31\u53d8\u6210\u4e86\u8ba9\u6bcf\u4e2a\u7ad9\u70b9\u5168\u90e8\u90fd\u4e3a\u6b63\u53cd\u9988\u624d\u4e3a\u771f<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>\u8bba\u6587\uff1a- Huang, Qun, and Patrick PC Lee. &#8220;Ld-sketch: A distributed sketching design for accurate and scalable anomaly detection in network data streams.&#8221; IEEE INFOCOM 2014-IEEE Conference on Computer Communications. IEEE, 2014.<\/p><\/blockquote>\n\n\n\n<p><\/p>\n<\/div><\/div>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"MV_Sketch\"><\/span><strong>MV Sketch<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u6211\u4eec\u53d1\u73b0ldsketch\u7684\u52a8\u6001\u5185\u5b58\u96be\u4ee5\u5b9e\u73b0\uff0c\u6539\u7b97\u6cd5\u91c7\u7528\u4e86\u8f83\u5c0f\u7684\u9759\u6001\u5185\u5b58\u6784\u5efa<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/img1.sdnlab.com\/\/wp-content\/uploads\/2019\/09\/03\/MV-Sketch001-.png\" alt=\"\" width=\"538\" height=\"170\"\/><\/figure><\/div>\n\n\n<p>\u6211\u4eec\u53d1\u73b0\u5bf9\u4e8e\u4e00\u4e2a\u6876\u9996\u5148\u5f53\u6876\u6570\u591f\u591a\u65f6\u57fa\u672c\u6700\u591a\u53ea\u5b58\u5728\u4e00\u4e2a\u5927\u6d41\uff0c\u5e76\u4e14\u8fd9\u4e2a\u5927\u6d41\u5fc5\u7136\u5360\u636e\u5927\u90e8\u5206\u6bd4\u4f8b<\/p>\n\n\n\n<p>\u56e0\u6b64\u4e0eLDsketch\u7c7b\u4f3c\uff0c\u6211\u4eec\u5bf9\u4e8e\u6bcf\u4e2a\u6876\u53ea\u65b0\u589e\u7ef4\u62a4heavy flow\u7684\u952e\u503c\u548c\u5bf9\u5e94Misra-Gries\u7b97\u6cd5\u7684\u4f30\u503c\u8ba1\u6570\u5668\uff0c\u4e0d\u8fc7\u6211\u4eec\u4ec5\u5b58\u6700\u5927\u503c\u4e14\u628a\u52a0\u51cf1\u53d8\u6210\u4e86\u5bf9\u5e94val<\/p>\n\n\n\n<p>\u5bf9\u4e8e\u67e5\u8be2\u64cd\u4f5c\u6211\u4eec\u5373\u8fd4\u56de\u76f8\u5e94\u4f30\u503c<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/img-blog.csdnimg.cn\/20201104202426346.png?x-oss-process=image\/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW94aXp4eng=,size_16,color_FFFFFF,t_70#pic_center\" alt=\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\" width=\"607\" height=\"312\"\/><\/figure><\/div>\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>\u8bba\u6587\uff1a- Tang, Lu, Qun Huang, and Patrick PC Lee. &#8220;Mv-sketch: A fast and compact invertible sketch for heavy flow detection in network data streams.&#8221; IEEE INFOCOM 2019-IEEE Conference on Computer Communications. IEEE, 2019.<\/p><\/blockquote>\n<\/div><\/div>\n\n\n\n<p><\/p>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"FlowRadar\"><\/span><strong>FlowRadar<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u8be5\u7b97\u6cd5\u4e3b\u8981\u4e3a\u5c0f\u5185\u5b58\u6765\u5b58\u50a8\u6570\u636e\u6d41\u8ba1\u6570\u5668\u5e76\u901a\u8fc7\u89e3\u7801\u6765\u5206\u6790\u6570\u636e\u6d41\u3002\u8fd9\u6837\u663e\u7136\u6211\u4eec\u5c31\u9700\u8981\u8bb0\u5f55\u5bf9\u5e94\u7684key\u3002\u90a3\u4e48\u4e3a\u4e86\u53ef\u4ee5\u89e3\u7801\uff0c\u6211\u4eec\u9700\u8981\u4f7f\u7528\u53ef\u9006\u7684\u538b\u7f29\u65b9\u5f0f\uff0c\u5c31\u662f\u52a0\u6cd5\u548c\u7684\u7ec4\u5408\u5f02\u6216\u3002<\/p>\n\n\n\n<p>\u5bf9\u4e8e\u66f4\u65b0\u64cd\u4f5c\uff0c\u6211\u4eec\u9996\u5148\u5229\u7528bloom filter\u6765\u8bb0\u5f55\u5b58\u5728\u591a\u5c11\u4e2a\u4e0d\u540c\u7684\u6d41\uff0c\u5373\u662f\u5426\u4e3a\u65b0\u7684key\uff0c\u4e4b\u540e\u5229\u7528CM\u8ba1\u6570\uff0c\u540c\u65f6\u6211\u4eec\u7ef4\u62a4\u5bf9\u4e8ekey\u7684\u4fe1\u606f\uff0c\uff08\u56e0\u4e3aCM\u8fdb\u884c\u591a\u6b21\u54c8\u5e0c\u5b58\u5728\uff09\u6211\u4eec\u5bf9\u4e8e\u6bcf\u4e2acounter\u90fd\u5b58\u4e00\u4e2a\u5bf9\u5e94key\u7684\u5b89\u4f4d\u5f02\u6216\u503c\uff0c\u4e5f\u5c31\u662f\u8bf4\u6bcf\u8fdb\u5165\u7684\u4e00\u4e2a\u65b0\u7684key\u90fd\u4e0e\u4e4b\u524d\u7684\u4fe1\u606f\u8fdb\u884c\u5f02\u6216\uff0c\u540c\u65f6\u6211\u4eec\u4e5f\u5b58\u50a8\u6709\u51e0\u4e2a\u4e0d\u540c\u7684key<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/kylelv.com\/wp-content\/uploads\/2021\/09\/image-1024x715.png\" alt=\"\" class=\"wp-image-872\" width=\"423\" height=\"295\" srcset=\"https:\/\/blog.kylelv.com\/wp-content\/uploads\/2021\/09\/image-1024x715.png 1024w, https:\/\/blog.kylelv.com\/wp-content\/uploads\/2021\/09\/image-300x209.png 300w, https:\/\/blog.kylelv.com\/wp-content\/uploads\/2021\/09\/image-768x536.png 768w, https:\/\/blog.kylelv.com\/wp-content\/uploads\/2021\/09\/image.png 1318w\" sizes=\"auto, (max-width: 423px) 100vw, 423px\" \/><\/figure><\/div>\n\n\n<p>\u90a3\u4e48\u8fd9\u6837\u6211\u4eec\u5982\u679c\u5b58\u5728\u4e00\u4e9b\u6876\u53ea\u6709\u4e00\u4e2akey\uff0c\u90a3\u4e48\u4ed6\u5b58\u7684\u5bf9\u5e94\u503c\u5fc5\u4e3a\u5176\u7684\u7cbe\u786e\u4fe1\u606f\uff0c\u6211\u4eec\u5c31\u53ef\u4ee5\u5229\u7528\u8fd9\u4e2a\u4fe1\u606f\u7ee7\u7eed\u6062\u590d\u5176\u4ed6\u6570\u636e\u3002\u5373\u6211\u4eec\u53ef\u4ee5\u5c06\u5176\u5bf9\u5e94\u7684\u6240\u6709\u6876\u90fd\u5220\u53bb\u8be5\u503c\u7684\u4fe1\u606f\uff0c\u8fd9\u6837\u4e5f\u5c31\u6709\u53ef\u80fd\u4f1a\u518d\u6709\u4e00\u4e9b\u6876\u53ea\u5269\u4e00\u4e2akey\uff0c\u5982\u6b64\u5f80\u590d\u4e00\u76f4\u5230\u6062\u590d\u4e0d\u4e86\u6216\u8005\u7ed3\u675f\u3002<\/p>\n\n\n\n<p>\u90a3\u4e48\u8fd9\u6837\u4e5f\u663e\u7136\u5bf9\u4e8e\u5206\u5e03\u5f0f\u673a\u5668\u4e5f\u5f88\u65b9\u4fbf\uff0c\u6211\u4eec\u5c06\u672c\u5730\u7684\u53ef\u89e3\u6570\u636e\u53d1\u7ed9\u5176\u4ed6\u4eba\u6765\u5229\u7528\u8fd9\u4e2a\u4fe1\u606f\u7ee7\u7eed\u89e3\u7801\uff0c\u8fd9\u6837\u4e0d\u65ad\u5faa\u73af\u76f4\u5230\u6ca1\u6709\u65b0\u7684\u53ef\u89e3\u7801\u6570\u636e<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>\u8bba\u6587\uff1a- Li, Yuliang, et al. &#8220;Flowradar: A better netflow for data centers.&#8221; 13th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 16). 2016.<\/p><\/blockquote>\n<\/div><\/div>\n\n\n\n<p><\/p>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"UnivMon\"><\/span><strong>UnivMon<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/kylelv.com\/wp-content\/uploads\/2021\/08\/image-2-1024x356.png\" alt=\"\" class=\"wp-image-865\" width=\"662\" height=\"230\" srcset=\"https:\/\/blog.kylelv.com\/wp-content\/uploads\/2021\/08\/image-2-1024x356.png 1024w, https:\/\/blog.kylelv.com\/wp-content\/uploads\/2021\/08\/image-2-300x104.png 300w, https:\/\/blog.kylelv.com\/wp-content\/uploads\/2021\/08\/image-2-768x267.png 768w, https:\/\/blog.kylelv.com\/wp-content\/uploads\/2021\/08\/image-2.png 1358w\" sizes=\"auto, (max-width: 662px) 100vw, 662px\" \/><\/figure><\/div>\n\n\n<p>\u4e3b\u8981\u601d\u60f3\u5c31\u662f\u5206\u5c42\u964d\u91c7\u6837\uff0c\u6309\u7167\u6570\u636e\u6d41\u5927\u5c0f\u6765\u5206\u6210log\u5c42\uff0c\u6bcf\u6b21\u4e8c\u5206\u4e4b\u4e00\u7684\u6982\u7387\u968f\u673a\u9009\u53d6\u8fdb\u884c\u91c7\u6837\uff0c\u8fd9\u6837\u6211\u4eec\u5f97\u5230\u4e86log\u4e2a\u5b50\u6d41\uff0c<\/p>\n<\/div><\/div>\n\n\n\n<p><\/p>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"ElasticSketch\"><\/span><strong>ElasticSketch<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p><\/p>\n<\/div><\/div>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u57fa\u6570\u4f30\u8ba1\u7b97\u6cd5 Linear Counting \u8be5\u7b97\u6cd5\u7528\u4e8e\u4f30\u6d4b\u6570\u636e\u57fa\u6570\uff0c\u4e5f\u5c31\u662f\u8bf4\u6709\u591a\u5c11\u4e0d\u540c\u5143\u7d20\uff0c\u91c7\u7528\u65b9\u6cd5\u975e\u5e38\u7b80\u5355 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[87,88],"class_list":["post-807","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-sketch","tag-88"],"_links":{"self":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/807","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=807"}],"version-history":[{"count":39,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/807\/revisions"}],"predecessor-version":[{"id":892,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/807\/revisions\/892"}],"wp:attachment":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=807"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=807"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=807"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}