计算机科学家发明一种高效的计数新方法 | 《量子杂志》

主要观点:团队利用随机性创建了一个简单算法,用于估计数据流中大量不同对象的数量。
关键信息

  • 以在雨林进行野生动物普查或 Facebook 统计每日登录用户为例,说明传统方法在处理大量数据时的困难。
  • 介绍 CVM 算法,其能解决长达 40 多年的不同元素问题,只需记住少量条目。
  • 以听《哈姆雷特》 audiobook 为例,阐述 CVM 算法的操作步骤,通过多次随机选择来估计不同单词的数量。
  • 数学证明该技术的准确性随内存大小而变化,实验表明不同内存大小下的平均估计值接近真实值。
    重要细节
  • CVM 算法由印度统计研究所的 Sourav Chakraborty、内布拉斯加林肯大学的 Vinodchandran Variyam 和多伦多大学的 Kuldeep Meel 创立。
  • 听《哈姆雷特》时,先在内存(白板)中记录前 100 个单词,然后根据硬币正反面决定是否保留,后续 rounds 中保留单词的条件逐渐变难,最终根据剩余单词数量和概率来估计不同单词的数量。
阅读 7
0 条评论