一种基于滑动窗口的数据流摘要构造算法

由于数据流具有无限、高速等特性,使得对数据流的查询处理往往不是面向整个数据流,而是把查询处理的范围限定在某个可操作的范围内,比如一个数据窗口。另一方面,通过数据摘要近似表达数据,也是数据流查询处理应对存储空间约束的常用策略。本文提出一种基于滑动窗口的数据流小波摘要构造算法,利用了窗口技术与数据摘要技术的优点。算法的基本思路是基于滑动窗口模型,将数据流划分成若干等宽基本窗口,每个基本窗口内数据进行小波分解与系数约简,从而形成滑动小波摘要窗口。为使窗口内数据摘要绝对重构误差最优,定义一个系数删减标准,采用贪心策略对窗口内小波系数逐步求精,从而获得最优绝对误差小波摘要。实际应用结果证明了算法的有效性。     

一种基于滑动窗口的数据流相似性查询算法

相似性查询是一种非常重要的数据挖掘应用。由于数据流具有无限、高速等特性,传统的查询算法不能直接应用于数据流。提出了一种基于小波滑动窗口的多数据流相似性查询算法。算法首先将滑动窗口划分成若干等宽基本窗口,然后对每个基本窗口内的数据进行小波分解与系数约简,从而形成小波摘要窗口。执行相似性查询时,直接基于小波摘要进行计算,而无需数据重构。由于利用了小波分解的线性处理优点,算法具有较低的时间复杂度。最后,基于实际数据对算法进行了实验,实验结果证明了算法的有效性。     

基于局部聚类的轨迹数据流偏倚采样

移动对象轨迹数据管理是移动计算领域的研究热点。通过采样技术构造数据流摘要是普通采用的方法之一。传统的均匀采样往往容易丢失某些关键变化数据。利用轨迹数据流的局部连续性特征,提出一种基于滑动窗口的偏倚采样算法。算法将滑动窗口通过聚类划分成若干大小不一的基本窗口,并针对每个基本窗口给定一个采样率,对窗口内数据进行偏倚采样,从而形成数据流摘要。算法利用了轨迹数据的内在特征,因此具有较高的采样质量。最后,基于实际数据对算法进行了实验,结果证明了算法的有效性。     

基于倾斜时间窗口的高效数据流偏向最近聚类分析算法

提出一种基于倾斜时间窗口的数据流偏向最近聚类算法。该算法首先通过将滑动窗口中数据等长分割形成不重叠的数据块——基本窗口,然后对每一基本窗口以Haar小波变换提取窗口数据的特征,通过改变所取各基本窗口小波变换系数个数达到保留较多最近数据细节特征的目的,即对于越近的基本窗口保留越多的小波系数而越旧的基本窗口保留越少的小波系数,最后通过定义数据流偏向最近距离,完成基于倾斜时间窗口的偏向最近聚类算法。该算法计算速度快,能高效地实现数据流偏向最近聚类分析。仿真实验验证了该算法的有效性。     

基于滑动窗口的数据流压缩技术及连续查询处理方法

基于滑动窗口的连续查询处理是数据流研究领域的一个热点问题．已有的研究工作均假设滑动窗口内的数据能够全部保存在主存中，若滑动窗口内的数据量超过了可用主存空间，已有的查询处理方法则无法正常工作．提出两种数据流上的滑动窗口压缩技术，有效地降低了滑动窗口的存储空间需求．同时，给出了基于压缩滑动窗口的连续查询处理算法，理论分析和实验结果表明，这些算法具有很好的性能，能够满足数据流连续查询处理的实时性要求．     

基于Voronoi图的组最近邻查询

组最近邻查询由于涉及多个查询点,因此比传统的最近邻查询更为复杂.充分考虑查询点的分布特征以及它们构成的几何图形的性质和特点,给出组最近邻所应满足的条件及判断组最近邻的理论方法.提出基于Voronoi图的组最近邻查询的VGNN算法,可以精确求解查询点集的最近邻.对于查询点不共线的情况,该算法的查询方式是以一点为中心、向外扩张式的;对于查询点共线的情况,该算法给出搜索范围,限定了参与计算的数据点的个数.给出基于Voronoi图的VTree索引.实验结果表明,基于VTree索引的VGNN算法具有较好的性能,并且当查询点不共线时,其性能具有较高的稳定性.     

基于空间填充曲线网格划分的最近邻查询算法

在建树过程中,R树存在最小边界矩形之间重叠的现象。当数据量较大时,重叠现象尤为严重,基于R树最近邻查询算法的性能急剧恶化。针对该问题,利用空间填充曲线的降低维度特性和数据聚类特性,提出一种基于网格划分最近邻查询算法。该算法将整个数据空间划分成大小相等、互不重叠的网格,对网格中的点进行线性排序之后,只需要访问查询点所在网格中的点及其周边邻近网格中的点,就能够获得最近邻。在Hilbert曲线、Z曲线和Gray曲线上实现3种最近邻查询算法,在映射算法和数据聚类特性上实验比较3种曲线之间的性能差异。实验结果表明,算法的查询性能明显优于顺序扫描算法和基于R树的最近邻查询算法。     

球面上的K最近邻查询算法

针对球面上数据对象点集的特征和K最近邻查询的需求,提出2种处理球面上K最近邻查询的算法:基于查询轴的K最近邻查询算法(PAM方法)和基于查询圆面的K最近邻查询算法(PCM方法).对2种算法进行实验比较,结果表明,PAM方法和PCM方法都适合处理球面上的最近邻查询问题,PAM方法在存储量和查询复杂度方面相对于PCM方法具...     

挖掘滑动窗口中的数据流频繁项算法

滑动窗口是一种对最近一段时间内的数据进行挖掘的有效的技术,本文提出一种基于滑动窗口的流数据频繁项挖掘算法.算法采用了链表队列策略大大简化了算法,提高了挖掘的效率.对于给定的阈值S、误差ε和窗口长度n,算法可以检测在窗口内频度超过Sn的数据流频繁项,且使误差在εn以内.算法的空间复杂度为O(ε-1),对每个数据项的处理和查询时间均为O(1).在此基础上,我们还将该算法进行了扩展,可以通过参数的变化得到不同的流数据频繁项挖掘算法,使得算法的时间和空间复杂度之间得到调节.通过大量的实验证明,本文算法比其它类似算法具有更好的精度以及时间和空间效率.     

基于滑动窗口的在线数据流增量聚集查询

增量查询技术由于能有效处理大量、快速、源源不断到达的数据流，因此备受关注。滑动窗口是动态数据流环境下的一种典型的窗口类型。该文研究了基于滑动窗口的数据流聚集查询，提出了一种新的增量聚集查询算法，采用了多种增量计算方法和查询共享技术，实现了多窗口资源共享。实验验证了该方法的有效性。     

带权值数据流滑动窗口随机抽样算法的改进

通过改进加权抽样算法,结合基本窗口技术,提出了两种面向带权值数据流上连续更新滑动窗口的随机抽样算法：WRSB算法和IWRSB算法。当新的数据元组到达时,根据数据元组的权值计算出该元组的键值,根据元组键值的大小决定其是否进入样本集以及样本集中被替换的数据元组,同时设置一个系统缓冲区来保存最近到达的键值较大的部分数据元组,作为过期数据元组的后备,使算法能够有效地处理过期数据元组问题。理论分析和实验结果表明,两种算法都能有效地处理带权值数据流上连续更新滑动窗口的随机抽样问题,相比较而言,IWRSB算法具有更好的性能。     

经验模态分解在数据流概要生成中的应用

由于流数据无限增长的特点,系统无法在内存中保存所有扫描过的流数据,因此数据流处理的关键是建立流数据的概要结构,以便随时能根据该结构提供数据流的近似处理结果,将重点讨论数据流的概要生成技术。先利用经验模态分解方法提取流数据的趋势,滤除数据中的噪声,再利用精确抽样方法实现概要的生成。利用提出的概要生成方法,内存中只需保存滑动窗口中多个段的概要信息。由于该方法中概要是基于趋势序列生成的,趋势序列较原序列平滑,序列中具有相同数值的元素增加,可以进一步节省存储空间。     

基于数据流频繁闭合模式的挖掘

用挖掘频繁闭合模式集代替挖掘频繁模式集是近年来提出的一个重要策略。根据数据流的特点,提出了一种基于滑动窗口的频繁闭合模式的新方法DSFC_Mine。该算法以滑动窗口中的基本窗口为更新单位,利用改进的CHARM算法计算每个基本窗口的潜在频繁闭合项集,将它们存储到一种新的数据结构中,利用该数据结构可以快速地挖掘滑动窗口中的所有频繁闭合项集。实验验证了该算法在时间上和空间上的可行性和有效性。     

基于衰减滑动窗口数据流聚类算法研究

数据流具有数据流量大、流量连续且快速、难以存储和恢复等特性,其挖掘质量和效率是检验挖掘算法的重要标准.传统的数据流聚类挖掘算法是基于界标窗口、滑动窗口和衰减窗口模型,其算法的聚类质量较差,时间复杂度高等不足,就此类问题,研究一种滑动衰减窗口的数据流聚类算法,并对算法进行了设计与实现,有效的改善传统数据流算法聚类质量和时间效率的问题.仿真实验结果表明了该算法的有效性,达到了较满意的效果.     

基于滑动窗口的XML数据流聚类算法

通过对XML数据流的聚类研究,提出一种基于滑动窗口的XML数据流聚类算法SW-XSCLS。该算法采用滑动窗口技术,以聚类特征指数直方图作为概要数据结构,能动态地淘汰“过时”的数据,较好地保存当前窗口内的数据分布状况,从而获取较高质量的聚类结果。理论分析和实验结果表明,该算法可以获得较高的聚类质量和较快的处理速度。     

基于加权移动平均的数据流预测模型*

提出一种新的基于滑动窗口的预测模型。该模型仅存储当前滑动窗口中的数据并对其进行分析,提高了计算效率;同时,为了削减在较小数据集上回归预测所产生的偏差,提出一种基于加权移动平均的数据流预测算法WMA_LRA。实验采用FDS 4.0模拟一个房屋的火灾发生情况,运用WMA_LRA算法对火灾现场的局部温度进行短期预测,结果表明该算法可以有效地提高计算效率和预测精度。