论文部分内容阅读
摘 要：本文研究了数据流概要数据的合并性，合并性就是给出两个数据集上的两个数据概要，存在一种方法可以将两个概要合并成两个数据集并集上的单一概要信息，同时不增加概要的大小或其近似误差，并可应用于数据流的近似处理查询。
关键词：数据流；概要；合并性
1 引言
数据概要对于大规模数据集查询是一个重要的手段，尤其是数据分布在网络中或是动态变化的，依据全部数据进行计算是无法实行的。在这种情况下，计算数据集D上的一个简洁的概要是可行的，且其保留了它的重要属性，同时可以使用概要来回答查询，而且占用资源少得多。由于概要具有更小的尺寸，还可以近似的回答查询，同时在概要的大小和近似误差之间存在一个权衡。目前各种各样的概要都被提出，像heavy hitters、分位数概要、柱状图、各种略图和草图的统计概要，像ε-近似和ε-内核的几何概要，像distance oracles的图形概要。注意对于不同类型的概要，误差参数ε总有不同的解释。
2 数据概要的合并性
合并性就是指给出两个数据集上的两个数据概要，存在一种方法可以将两个概要合并成两个数据集并集上的单一概要信息，同时不增加概要的大小或其近似误差。这个性质意味着数据概要也可以像Sum和Max聚合函数那样的代数运算一样可以通过某种方法合并。几类数据概要可以通过构造直接合并，最明显的就是略图，其是具有线性功能的数据集，但是其他的像heavy hitters和分位数一些基本的概要不能被合并。具体来说，对于ε-近似heavy hitters来说，存在一个大小为o（1/ε）的确定的合并概要；对于ε-近似分位数来说，存在一个大小为 的具有受限制的合并性质的确定概要和大小為 具有完全合并性质的随机概要。这个成果也可以应用到几何概要中，例如ε-近似和ε-内核。
3 概要合并的应用
⑴分布式计算。合并操作是由MUD（大规模无序分布）模型计算所引起，其描述了大规模分布式编程范例像MapReduce和Sawzall。在这种模型中，输入数据被分解成任意块，其中的每个块可能由不同的机器来处理。每块数据第一次由本地函数处理，输出信息，然后所有的这些在任意形式下使用聚合函数两两组合，最终产生一个总体信息。最后应用后期处理步骤，这实际上相当于合并性的概念，其中每台机器建立一个共享输入的概要，聚合函数就是合并操作，后期处理步骤相当于形成关于概要的查询。主要结论就是任何定义在所有输入上的计算对称函数的确定性流算法都可以由MUD算法来模拟，但这个结论并不适用于不确定性函数，即函数可能由许多正确的输出。许多概要计算的流行算法都是不确定性的，所以这个结论并不适用于所有案例。
⑵网络聚合。在传感器网上的节点组织成一个路由树，根在基站。每个传感器都有一些数据且数据聚合的目标是为了计算所有数据的概要。几乎所有的数据聚合算法都遵循一个自底向上的方法：从叶子开始，聚合传送到根。当一个节点收到来自它的孩子的概要，它将会把它们合并成自己的概要，并将结果传送到它的父亲。根据传感器的物理分布，路由树可能是任意形状。如果概要的大小不依赖于|D|，那么这将形成负载均衡，沿着每个分支的通信是相同的，而不是将更多的负载放在靠近根部的边上。
4 合并算法描述
出于以上及其他方面的应用，本文提出了有效的合并算法。其中用是S（）来表示一个概要方法，涉及D和误差参数ε，s（）可能由许多有效输出（即根据处理D的顺序，它可能返回不同有效ε-概要），即s（）可能是一对多的映射。用S（D，ε）来表示数据集D的任意有效概要，且具有由这些方法产生的误差ε，同时用k（n，ε）表示包含N个项目的数据集D的任意S（D，ε）的最大尺寸。
如果存在一个算法A，它能从任意两个输入概要S（D1，ε）和S（D2，ε）产生一个概要S（D1 D1，ε），那么就说S（）是可以合并的。
通过算法A合并产生概要的大小至多是k（|D1|+|D2|，ε）。如果k（n，ε）不依赖于n，就可以通过k（ε）来表示，那么S（D1，ε）和S（D2，ε）中的每一个的大小和由A产生的概要的大小至多是k（ε）。在某种意义上说，合并算法A可能代表概要S（D，ε）或可能储存一些额外的信息（如加快合并过程的一个数据结构），还将用S（D，ε）标识概要的一些表示，还包含额外信息的维持。
如果限制输入，以使|D2|=1，即每次总是合并单一项，然后恢复流模式。S（D，ε）就是通过流算法维持的概要，算法A针对每个新到达的对象进行概要更新。因此，合并性比流具有更强的严格要求，概要的大小应该至少是一样大。
5 结束语
一些数据概要可以被合并。例如，所有D上具有线性函数的略图都可以直接合并，主要包括F2 AMS略图，Count-Min略图，略图，还有许多其他的。能维持最大值或top-k值的概要也可以直接合并，尤其是估算不同元素数量的概要。然而，几个基于其他技术的概要不能被合并或具有不令人满意的界限。
关键词：数据流；概要；合并性
1 引言
数据概要对于大规模数据集查询是一个重要的手段，尤其是数据分布在网络中或是动态变化的，依据全部数据进行计算是无法实行的。在这种情况下，计算数据集D上的一个简洁的概要是可行的，且其保留了它的重要属性，同时可以使用概要来回答查询，而且占用资源少得多。由于概要具有更小的尺寸，还可以近似的回答查询，同时在概要的大小和近似误差之间存在一个权衡。目前各种各样的概要都被提出，像heavy hitters、分位数概要、柱状图、各种略图和草图的统计概要，像ε-近似和ε-内核的几何概要，像distance oracles的图形概要。注意对于不同类型的概要，误差参数ε总有不同的解释。
2 数据概要的合并性
合并性就是指给出两个数据集上的两个数据概要，存在一种方法可以将两个概要合并成两个数据集并集上的单一概要信息，同时不增加概要的大小或其近似误差。这个性质意味着数据概要也可以像Sum和Max聚合函数那样的代数运算一样可以通过某种方法合并。几类数据概要可以通过构造直接合并，最明显的就是略图，其是具有线性功能的数据集，但是其他的像heavy hitters和分位数一些基本的概要不能被合并。具体来说，对于ε-近似heavy hitters来说，存在一个大小为o（1/ε）的确定的合并概要；对于ε-近似分位数来说，存在一个大小为 的具有受限制的合并性质的确定概要和大小為 具有完全合并性质的随机概要。这个成果也可以应用到几何概要中，例如ε-近似和ε-内核。
3 概要合并的应用
⑴分布式计算。合并操作是由MUD（大规模无序分布）模型计算所引起，其描述了大规模分布式编程范例像MapReduce和Sawzall。在这种模型中，输入数据被分解成任意块，其中的每个块可能由不同的机器来处理。每块数据第一次由本地函数处理，输出信息，然后所有的这些在任意形式下使用聚合函数两两组合，最终产生一个总体信息。最后应用后期处理步骤，这实际上相当于合并性的概念，其中每台机器建立一个共享输入的概要，聚合函数就是合并操作，后期处理步骤相当于形成关于概要的查询。主要结论就是任何定义在所有输入上的计算对称函数的确定性流算法都可以由MUD算法来模拟，但这个结论并不适用于不确定性函数，即函数可能由许多正确的输出。许多概要计算的流行算法都是不确定性的，所以这个结论并不适用于所有案例。
⑵网络聚合。在传感器网上的节点组织成一个路由树，根在基站。每个传感器都有一些数据且数据聚合的目标是为了计算所有数据的概要。几乎所有的数据聚合算法都遵循一个自底向上的方法：从叶子开始，聚合传送到根。当一个节点收到来自它的孩子的概要，它将会把它们合并成自己的概要，并将结果传送到它的父亲。根据传感器的物理分布，路由树可能是任意形状。如果概要的大小不依赖于|D|，那么这将形成负载均衡，沿着每个分支的通信是相同的，而不是将更多的负载放在靠近根部的边上。
4 合并算法描述
出于以上及其他方面的应用，本文提出了有效的合并算法。其中用是S（）来表示一个概要方法，涉及D和误差参数ε，s（）可能由许多有效输出（即根据处理D的顺序，它可能返回不同有效ε-概要），即s（）可能是一对多的映射。用S（D，ε）来表示数据集D的任意有效概要，且具有由这些方法产生的误差ε，同时用k（n，ε）表示包含N个项目的数据集D的任意S（D，ε）的最大尺寸。
如果存在一个算法A，它能从任意两个输入概要S（D1，ε）和S（D2，ε）产生一个概要S（D1 D1，ε），那么就说S（）是可以合并的。
通过算法A合并产生概要的大小至多是k（|D1|+|D2|，ε）。如果k（n，ε）不依赖于n，就可以通过k（ε）来表示，那么S（D1，ε）和S（D2，ε）中的每一个的大小和由A产生的概要的大小至多是k（ε）。在某种意义上说，合并算法A可能代表概要S（D，ε）或可能储存一些额外的信息（如加快合并过程的一个数据结构），还将用S（D，ε）标识概要的一些表示，还包含额外信息的维持。
如果限制输入，以使|D2|=1，即每次总是合并单一项，然后恢复流模式。S（D，ε）就是通过流算法维持的概要，算法A针对每个新到达的对象进行概要更新。因此，合并性比流具有更强的严格要求，概要的大小应该至少是一样大。
5 结束语
一些数据概要可以被合并。例如，所有D上具有线性函数的略图都可以直接合并，主要包括F2 AMS略图，Count-Min略图，略图，还有许多其他的。能维持最大值或top-k值的概要也可以直接合并，尤其是估算不同元素数量的概要。然而，几个基于其他技术的概要不能被合并或具有不令人满意的界限。