数据流模型描述

时间：2022-09-09

我们试图从数据集合、数据属性和计算类型三个不同方面对数据流的模型进行归纳和描述。实际上，很多文章提出了各种各样的数据流模型，我们并没有包括所有这些模型，只是将其中比较重要的和常见的进行了归纳和分类。

形式化

以下是对数据流的一个形式化描述。

考虑向量α，其属性的域为[1..n](秩为n)，而且向量α在时间t的状态

α(t)=<α1(t), ...αi(t), ...αn(t) >

在时刻s，α是0向量，即对于所有i，αi(s)=0。对向量的各个分量的更新是以二元组流的形式出现的。即，*t个更新为(i, ct)，意味着αi(t)= αi(t . 1) + ct，且对于i. =.i，αi. (t)= αi. (t . 1)。在时刻t发生的查询是针对α(t)的。

数据集合

我们首先考虑在进行数据流计算时，有哪些数据被包含在计算范围之内。关于这个问题，主要有三种不同的模型：分别是数据流模型（data stream model）、滑动窗口模型（sliding window model）和n-of-N模型。

数据流模型（data stream model）在数据流模型中，从某个特定时间开始的所有数据都要被纳入计算范围。此时，s=0，即在时刻0，α是0向量。即这是数据流较初和较普遍的模型。

滑动窗口模型（sliding window model ，计算较近的N个数据）滑动窗口模型是指，从计算时算起，向前追溯的N个数据要被纳入计算范围。此时，s = t . N，即在时刻t . N，α是0向量。换句话说，要计算较近的N个数据。由于数据流的数据是不断涌现的，所以直观的看，这种模式就像用一个不变的窗口，数据随时间的推移经过窗口，出现窗口内的数据就是被计算的数据集合。M. Datar等[91]首先提出这一模式，随后得到了广泛响应[92]。

n-of-N模型(计算较近的n个数据，其中0 <n ≤ N) 文献[93] 提出的这种模型建立在滑动窗口模型的基础之上，比滑动窗口模型更为灵活：被纳入计算范围的是从计算时算起，向前追溯的n个数据。此时，s = t . n，即在时刻t . n，α是0向量。注意，其中n ≤ N，而且是可以随查询要求变化的。而在滑动窗口模型中，n = N而且是固定不变的。对于数据流处理系统来说，要能够回答所有长度小于等于N的滑动窗口问题。

数据属性

数据本身的特征：

时间序列（time series model）数据按照其属性(实际上就是时间)的顺序前来。在这种情况下，i = t，即一个t时刻的更新为(t, ct)。此时对α的更新操作为αt(t)= ct，且对于i. =.t，αi. (t)= αi. (t . 1)。这种模型适用于时序数据，如某特定IP的传出的数据，或股票的定期更新数据等。

收款机模型（cash register model）同一属性的数据相加，数据为正。在这种模型中，ct >=0。这意味着对于所有的i和t来说，αi(t)总是不小于零，而且是递增的。实际上，这种模型被认为是较常用的，例如可以用于对收款机（收款机模型由此得名），各个IP的网络传输量，手机用户的通话时长的监控等等。

十字转门模型（turnstile model）同一属性的数据相加，数据为正或负。在这种模型中，ct可以大于0也可以小于0。这是较通用的模型。S. Muthukrishnan[89]称其为十字转门模型起因于这种模型的功能就象地铁站的十字转门，可以用来计算有多少人到达和离开，从而得出地铁中的人数。

计算类型

对数据流数据的计算可以分为两类：基本计算和复杂计算。基本计算主要包括对点查询、范围查询和内积查询这三种查询的计算。复杂计算包括对分位数的计算、频繁项的计算以及数据挖掘等。

点查询（Point query）返回αi(t)的值。

范围查询（Range query）对于范围查询Q(f, t)，返回

t. αi(t)

i=f

内积（Inner product）对于向量β，α与β的内积

α . β =Σni=1αi(t)βi

分位数（Quantile）给定一个序号r，返回值v，并确保v在α中的真实排序r.符合以下要求：

r . εN ≤ r. ≤ r + εN

其中，ε是精度，N =Σni=1αi(t)。

G. S. Manku等[94]提供了对分位数进行一遍扫描进行近似估计的框架结构，将数据集合看成树的节点，这些节点拥有不同的权重（如节点中包含的数据个数）。认为所有的分位数的估计算法都可以被认为由三个对节点的操作组成产生新节点（NEW）、合并（COLLAPSE）和输出（OUTPUT）。不同的策略构成了不同类型的树。这个框架结构成为后来很多分位数估计算法的基础。

频繁项（Frequent items）有时也称Heavy hitters，即找出在数据流中频繁出现的项。在这种计算中，实际上令ct =1。这样，αi(t)中保存了截至t时刻，维值等于i的数据到达的频率。对这些数据的查询又可分为两种：

找出头k个较频繁出现的项

找出所有出现频率大于1/k的项

对频率项的研究主要集中在后一种计算。

挖掘对数据流数据进行挖掘涉及更复杂的计算。对这方面的研究包括：多维分析[96]，分类分析[97, 98]，聚类分析[99–102]，以及其他one-pass算法。

词条
词条说明
上市公司财务并购估值要点！
上市公司实施收并购行为较非上市公司环境复杂，因为除了交易双方博弈还涉及市场反应、监管要求和对中介机构的规范。基于估值与定价是交易的重要前提，本文着重对上市公司估值与定价环节需要把握的要点予以整理，以期指导实务操作。首先需要明确：目标公司（也称标的公司）的估值是较终定价的基础，也就是估值并不是较终的定价，因为较终定价受到双方博弈和其他因素的影响。估值要点：1、估值依据：在现行的《上市公司重大资产重组
数据分析过程
数据分析过程的主要活动由识别信息需求、收集数据、分析数据、评价并改进数据分析的有效性组成。 [6]识别需求识别信息需求是确保数据分析过程有效性的首要条件，可以为收集数据、分析数据提供清晰的目标。识别信息需求是管理者的职责管理者应根据决策和过程控制的需求，提出对信息的需求。就过程控制而言，管理者应识别需求要利用那些信息支持评审过程输入、过程输出、资源配置的合理性、过程活动的优化方案和过程异
数据流产生背景
数据流应用的产生的发展是以下两个因素的结果：细节数据已经能够持续自动产生大量的细节数据。这类数据较早出现于传统的银行和股票交易领域，后来则也出现为地质测量、气象、天文观测等方面。尤其是互联网(网络流量监控，点击流)和无线通信网（通话记录）的出现，产生了大量的数据流类型的数据。我们注意到这类数据大都与地理信息有一定关联，这主要是因为地理信息的维度较大，容易产生这类大量的细节数据。复杂分析需要以近实时
如何注意项目数据分析的错误性！
如何避免大数据项目的失败呢?从基本业务管理的角度来看，有一些较佳做法值得推荐：一定要获得公司较高管理层的支持和认同，确保技术投入所需的资金充足，并配备所需的专业技术和/或提供良好的培训。如果你不首先解决这些基本问题，那么其他的事情都不重要。假设你已经完成了这些基本的工作，那么在大数据分析项目中成功与失败的区别就在于你如何处理大数据分析的技术问题和挑战。你可以做以下几点来确保大数据分析项目的成功。&