《大数据算法》一3.1 空间亚线性算法概述

本文涉及的产品
云原生大数据计算服务 MaxCompute,5000CU*H 100GB 3个月
云原生大数据计算服务MaxCompute,500CU*H 100GB 3个月
简介: 本节书摘来华章计算机《大数据算法》一书中的第3章 ,第3.1节,王宏志 编著, 更多章节内容可以访问云栖社区“华章计算机”公众号查看。 第3章 空间亚线性算法 3.1 空间亚线性算法概述 空间亚线性算法指的是在算法运行过程中需要的空间小于数据量的实际存储空间,在一些情况下,空间亚线性算法也叫作数据流算法。

本节书摘来华章计算机《大数据算法》一书中的第3章 ,第3.1节,王宏志 编著, 更多章节内容可以访问云栖社区“华章计算机”公众号查看。

第3章 空间亚线性算法

3.1 空间亚线性算法概述

空间亚线性算法指的是在算法运行过程中需要的空间小于数据量的实际存储空间,在一些情况下,空间亚线性算法也叫作数据流算法。因此我们首先介绍数据流模型。
1.数据流模型
数据流,顾名思义指的是流动的、源源不断的数据,这些数据只能顺序扫描一次或几次。因为数据是流起来的,所以只能顺序扫描,且只能扫描常数次。这意味着对于这样的数据,时间复杂度超过O(n)的算法是不可行的,而且能够使用的内存是有限的。注意,“有限”指的是数据可能无限增大,但是能够使用的内存是有限的,这就导致空间要求是亚线性的,而且最好所需空间和数据量是无关的。
为了基于这个模型实现算法,通常的方法是维护一个中间的内存结果,一般称为数据略图,它给出的是数据相关性质的一个有效估计。而这个中间结果的数据量往往是比较小的,通常与整个数据集合的数据量无关。
由于如下两个方面的原因,数据流模型适用于大数据。第一,时间有保障,它顺序扫描数据仅一次。第二,内存要求低,通常是亚线性的。而且通过本节的一些实例可以看到,其内存需求量和数据量没有特别直接的关系。
数据流模型中的数据流指的是来自某个域中的元素序列,可以表示为image。注意后面的省略号,一些和序列有关的问题往往以xn结尾,但是对数据流模型没有xn,因为我们假定数据是源源不断到来的,没有结束。数据流模型的第二个要素是有限的内存,也就是内存的规模远小于全部数据需占用内存的规模。这意味着把数据全部放到内存中计算不可行,通常所需要的内存为image 若log计算中未标明底数,则默认底数为2。或image,甚至是一个常数。而且当新元素到来时,需要快速处理每个元素,因为元素到来的快慢是不一定的,可能速度非常快,留给每个元素的处理时间并不充足。
通常,我们感兴趣的函数是输入流σ的元素中多重集的统计属性,这个多重集可以用向量f=(f1,f2,…,fn)来表示,其中fj={i:ai=j}=σ中j出现的次数换句话说,σ隐式地定义了向量f,本章要讨论的是形式为Φ(f)的函数的计算。在处理这种流时,当我们扫描每一个符号j∈[n]时,计算结果是频率fj的一个增量,因此,可以认为σ是对于向量f的更新。
定义了这个概念后,我们要更多地考虑关于f的更新方法。比如,如果频率fj能够既是增加的又是减少的,并且由变量决定呢?这就引出了更加严格的模型。
定义3-1(十字转门模型) σ中的符号都属于[n]×{-L,…,L},解释如下:根据接收到的符号ai=(j,c)更新fj←fj+c。
向量f初始化为0。在这个广义的模型中,改变变量m的作用是很常见并且自然的想法:m不代表流的长度,而代表在某一时刻这个多重集的项的最大数目。更形式化地,在任何时候,有image这个模型的一种特殊情况叫作严格的十字转门模型,在这种模型下假定任何时候f≥0。一种更加严格的模型叫作现金注册模型,在这个模型中只考虑正数的更新,比如要求每一次更新(j,c)满足c>0。
2.数据流用途
那么,从数据流中计算什么?对数据库和算法理论有一些了解的读者可能知道,大概十年前数据流是数据库研究的热点之一,今天依然有很多人在研究。可以从数据流中计算和挖掘多种统计量,如最大值(max)、最小值(min)、和(sum)、平均值(avg)这些基本的聚集的值,也可以计算中位数、分位数、频繁元素等更复杂的统计量,还可以做一些分析、挖掘、预警等,这些工作都吸引了大量研究人员。
3.数据流算法质量分析
因为人们已经证明很多函数不能通过亚线性空间来求解,因而我们从数据流中计算出的函数Φ(σ)的值通常是一个接近Φ(σ)的估计。而在算法设计过程中,我们通常使用随机化的算法,尽管可能会导致一些错误,但都是可控制的。于是有了下列基本定义。
定义3-2 令A(σ)表示随机流算法A在输入σ时产生的输出。注意这是一个随机值。令Φ代表A要计算的函数。如果我们能够得到image则称算法A为(ε,δ)乘法近似Φ。如果我们能够得到image则称算法A为(ε,δ)加法近似Φ。
注意,上面的定义先强调了乘法的接近。但是当Φ(σ)接近或者等于0的时候,我们可能要用到加法的接近。
4.数据流实例
考虑一个数据流的实例:{32,112,14,9,37,83,115,2,…}。
对于这个数据流容易计算的函数包括:最大值,最小值,和,计数。保存“和”与“计数”,相除结果即为avg。处理这些函数时通常采用单个寄存器s,并直接更新寄存器s。如求最大值,首先把寄存器初始化为0,然后比较当前元素x和寄存器中s的大小,将较大的量放到寄存器s当中,计算结束。在任意时刻,寄存器s中保存的数据都是当前数据流中的最大值。
计算sum的方法类似。首先都是把s初始化为0,所不同的是对于每个接收的x,将x累加到寄存器s中。这样,在任何时刻单个寄存器s保存的数据就是当前到来的数据流的所有数据的和。
5.数据流合并
上面例子中的数据概要就是单个值寄存器s。寄存器s是可合并的,即从一部分数据流得到x1,从另一部分数据流得到x2,通过x1和x2的累加或比较就可以得到整个数据流中当前所有元素的结果。例如,第100个之前的数放在x1,第100个以后的数放在x2,则x1和x2可以合并。通过比较x1和x2的大小,较大者就是这200个数中的最大值。同样,和的略图也是可合并的。前100个数据和存于x1,100个以后的数据和存于x2,将x1和x2相加就是当前所有元素的和。

相关实践学习
基于MaxCompute的热门话题分析
本实验围绕社交用户发布的文章做了详尽的分析,通过分析能得到用户群体年龄分布,性别分布,地理位置分布,以及热门话题的热度。
SaaS 模式云数据仓库必修课
本课程由阿里云开发者社区和阿里云大数据团队共同出品,是SaaS模式云原生数据仓库领导者MaxCompute核心课程。本课程由阿里云资深产品和技术专家们从概念到方法,从场景到实践,体系化的将阿里巴巴飞天大数据平台10多年的经过验证的方法与实践深入浅出的讲给开发者们。帮助大数据开发者快速了解并掌握SaaS模式的云原生的数据仓库,助力开发者学习了解先进的技术栈,并能在实际业务中敏捷的进行大数据分析,赋能企业业务。 通过本课程可以了解SaaS模式云原生数据仓库领导者MaxCompute核心功能及典型适用场景,可应用MaxCompute实现数仓搭建,快速进行大数据分析。适合大数据工程师、大数据分析师 大量数据需要处理、存储和管理,需要搭建数据仓库?学它! 没有足够人员和经验来运维大数据平台,不想自建IDC买机器,需要免运维的大数据平台?会SQL就等于会大数据?学它! 想知道大数据用得对不对,想用更少的钱得到持续演进的数仓能力?获得极致弹性的计算资源和更好的性能,以及持续保护数据安全的生产环境?学它! 想要获得灵活的分析能力,快速洞察数据规律特征?想要兼得数据湖的灵活性与数据仓库的成长性?学它! 出品人:阿里云大数据产品及研发团队专家 产品 MaxCompute 官网 https://www.aliyun.com/product/odps 
相关文章
|
2月前
|
机器学习/深度学习 算法 搜索推荐
从理论到实践,Python算法复杂度分析一站式教程,助你轻松驾驭大数据挑战!
【10月更文挑战第4天】在大数据时代,算法效率至关重要。本文从理论入手,介绍时间复杂度和空间复杂度两个核心概念,并通过冒泡排序和快速排序的Python实现详细分析其复杂度。冒泡排序的时间复杂度为O(n^2),空间复杂度为O(1);快速排序平均时间复杂度为O(n log n),空间复杂度为O(log n)。文章还介绍了算法选择、分而治之及空间换时间等优化策略,帮助你在大数据挑战中游刃有余。
63 4
|
2月前
|
分布式计算 资源调度 Hadoop
大数据-80 Spark 简要概述 系统架构 部署模式 与Hadoop MapReduce对比
大数据-80 Spark 简要概述 系统架构 部署模式 与Hadoop MapReduce对比
69 2
|
2月前
|
存储 分布式计算 API
大数据-107 Flink 基本概述 适用场景 框架特点 核心组成 生态发展 处理模型 组件架构
大数据-107 Flink 基本概述 适用场景 框架特点 核心组成 生态发展 处理模型 组件架构
86 0
|
2月前
|
存储 分布式计算 算法
大数据-106 Spark Graph X 计算学习 案例:1图的基本计算、2连通图算法、3寻找相同的用户
大数据-106 Spark Graph X 计算学习 案例:1图的基本计算、2连通图算法、3寻找相同的用户
66 0
|
24天前
|
缓存 算法 大数据
大数据查询优化算法
【10月更文挑战第26天】
49 1
|
1月前
|
机器学习/深度学习 数据采集 算法
大数据中缺失值处理使用算法处理
【10月更文挑战第21天】
39 3
|
17天前
|
算法 C# 索引
C#线性查找算法
C#线性查找算法!
|
2月前
|
存储 消息中间件 大数据
大数据-68 Kafka 高级特性 物理存储 日志存储概述
大数据-68 Kafka 高级特性 物理存储 日志存储概述
30 1
|
2月前
|
机器学习/深度学习 算法 API
机器学习入门(五):KNN概述 | K 近邻算法 API,K值选择问题
机器学习入门(五):KNN概述 | K 近邻算法 API,K值选择问题
|
2月前
|
存储 分布式计算 NoSQL
大数据-144 Apache Kudu 基本概述 数据模型 使用场景
大数据-144 Apache Kudu 基本概述 数据模型 使用场景
39 0