学科分类 - 《中国大百科全书》第三版网络版

高级搜索

专业板块专题板块大众板块

首页 . 理学 . 计算机科学技术

流算法/ streaming algorithm // streaming algorithm /

在计算机科学中，流算法指在流式计算模型下、以数据流的形式处理大规模数据并从中获得有价值信息的算法。

图数据流算法/ graph stream algorithm /graph stream algorithm
流算法
数据流算法（见流算法）和图论相交叉产生的一个研究方向，其核心问题是设计算法用较少的空间解决与图相关的属性判定等各种问题。
略图构造/ sketching /sketching
流算法
略图构造（sketching）指的是利用略图设计流式算法（见流算法）的技巧。在设计流算法时，常常需要通过随机映射将数据流中的高维数据投影到在一个小的存储空间内作为概要，并基于该概要近似地回答有关整个数据流的特定查询。如果这个小空间存储的概要具有可合并性，则称其为一个略图。换言之，存在一个空间效率很高的算法将任意两个数据流的略图合并成一个关于整个数据流的略图。
布隆过滤器/ Bloom filter /Bloom filter
流算法
由B.H.布隆（Burton Howard Bloom）在1970年提出的一种具有空间高效性的概率型数据结构。它用来判断某一个元素是否属于某一个集合。布隆过滤器返回的结果允许存在误报，但是不允许漏报，也就是说，可以返回的是一个元素“可能在集合中”或者“一定不在集合中”。布隆过滤器可以插入元素但是不可以删除已有的元素，插入越多的元素，误报率越高。