数据流概要数据结构在大型零售商业管理信息系统中应用.docVIP

数据流概要数据结构在大型零售商业管理信息系统中应用 　　[摘要] 本文首先介绍了数据流概要数据结构构建技术及其发展现状，说明了数据流概要构建技术应用于大型零售商业管理信息系统中的必要性，分析了如何将数据流概要构建技术应用于大型零售商业管理信息系统中。 　　[关键词] 数据流 概要数据结构 零售商业 管理信息系统 　　 　　一、引言 　　 　　近年来在很多应用领域中出现了一种新的数据模式，其数据不是以传统的有限数据集形式，而是连续的数据流形式出现。这些应用领域包括金融数据在线分析、商业交易数据处理、传感器网络、电信数据管理和网络安全等。数据流中的数据基本元素仍然可能是关系元组，但数据的到达是快速、时变、不可预测和无限的数据流形式，不可能完全存储原始数据。但是，对于很多应用来说，查询历史数据却是很重要的。从而需要利用高效的近似处理算法，在有限的存储空间中，建立和维护一个数据量远远小于其原始数据规模的概要数据结构（Synopsis Data Structure）。数据流概要构建技术的研究当前数据流领域的研究热点之一，已经取得了一些研究成果。 　　 　　二、数据流概要数据结构 　　 　　根据所处理数据的时序范围，数据流处理模型可分为界标窗口模型模型（Landmark Window Model）、滑动窗口模型（Sliding Window Model）和快照模型（Snapshot Model）等多种子模。其中最常用的处理子模型是界标窗口模型模型和滑动窗口模型。界标窗口模型是指在内存中开辟一个内存空间，用来保存自某个初始时间点到当前时间点范围内到达的数据元组。滑动窗口模型是指在内存中开辟一个内存空间，用来保存最近到达的数据，随着新数据的不断到达，滑动窗口中的数据不断被更新。滑动窗口分为两类，一类是基于数据元组个数定义的滑动窗口，即在内存中保存数据流中数量为常数m的必威体育精装版到达的数据；另一类是基于时间定义的滑动窗口，即在内存中保存数据流在最近Δt时间范围内到达的数据。基于不同数据流处理子模型构建概要数据结构有不同的近似处理算法和技术，下面简单介绍几种常用的数据流概要数据结构构建方法和技术。 　　随机抽样方法从整个数据集中随机抽取一部分数据形成样本集来描述数据的总体分布，根据该样本集获得对数据总体的近似查询结果，是常用的基于界标窗口模型和滑动窗口模型概要数据结构构造方法。水库抽样（Reservoir Sampling）是一种经典的在线均匀抽样算法，可用于数据流的在线处理，可以适用于界标窗口模型，但不能有效地处理数据的过期删除，不适用于数据流滑动窗口处理子模型。链式抽样（Chain-Sample）算法针对水库抽样进行了改进，是一种适用于基于数据元组个数的滑动窗口的随机抽样算法。链式抽样方法利用多个数据元组的“链”来处理过期数据问题，能够获得整个滑动窗口上的一个样本集。优先级抽样（Priority-Sample）算法对每个数据元素随机赋给一个0到1之间的优先级数值，然后根据数据元组的优先级数值和到达的时间先后来进行排序，根据其顺序来对样本集进行插入和删除的维护。上述两种抽样算法属于均匀抽样，以相同的概率对数据流中到达的数据元组进行随机抽样，文献通过对水库抽样算法的改进，给出了加权抽样算法，该算法只需单遍扫描整个数据集就能实现对带权值数据流中数据元组的随机抽样，是一种偏倚抽样算法。 　　直方图方法是根据实际数据的分布将数据划分到一系列的区间（直方或桶）中，以桶为单位估算数据的分布。根据桶内数据的分布情况，直方图一般可分为等宽、变宽、偏向两端等各种类型。其中变宽直方图又有等深（或等高）、V-最优、压缩、最大差异直方图等各种类型。直方图可以简洁地表达一个数据集中数据值的分布情况，在传统数据领域有着广泛的应用，有很多最优直方图和逼近最优直方图的构造算法。但这些算法不能适用于数据流的处理。Guha等中把面向数据流的直方图算法按照估算数据的不同范围分为两类：Agglomerative类算法和Fixed Window类算法，并且通过改进V-最优直方图维护算法，降低算法的空间和时间复杂度以适应数据流的处理，提出了一种Fixed Window类直方图增量维护算法，在文献提出了一种Agglomerative类直方图维护算法，构造V-最优直方图的1＋ε逼近，但该算法仅仅适用于经过数据排序的流数据处理，并且不能对直方图进行增量维护；Datar等提出了一种统计直方图，称为指数直方图（EM, Exponential Histogram），EM按照数据元组到达的顺序构建桶，可用于建立和维护基于滑动窗口模型的概要数据结构。 　　除随机抽样和直方图外，Sketches技术、基本窗口和小波变换等也是构建数据流概要结构的常用方法和技术[6]。 　　 　　三