滑动窗口(数据库)
时间：2022-12-25 20:30:01 | 来源：信息时代
时间：2022-12-25 20:30:01 来源：信息时代
滑动窗口 : 数据流系统在内存中开辟的区间,该区间只保存最近一段时间内到达的数据流数据,并随着新数据到来,窗口不断向前滑动,用新数据替换旧数据,以实时地支持查询请求。例如,设S={…,at-1,at,at+1,…}为一个数据流,T为一个时间长度,t>T是一个变化的时刻,t和T具有相同的度量单位,则S的一个时间间隔为T的滑动窗口可表示为S[t-T:t]。数据流系统可以同时存在多个数据流和多个滑动窗口,同一个滑动窗口可以被多个不同的连续查询共享,同一个连续查询也可能查询多个滑动窗口中的数据。
传统数据库中的数据是静态有界的,所以各种查询操作可以处理全部数据,而数据流通常具有动态和无界的特性,系统无法一次性处理全部数据,而某些查询操作所处理的对象必须有界,因此,数据流上的查询多为基于窗口的查询。
数据流是无界的,而数据流处理的某些操作如连接,只能在数据流的有限窗口内运行。为支持各种不同类型的查询要求,必须建立多样化的窗口模型来处理数据流中已到达的和即将到达的数据部分; 同时要提供灵活的窗口机制传递查询结果,使查询结果可直接呈现给用户或由用户根据需要取出。窗口是数据流有限部分的历史性快照,从这种意义上可把窗口分为: 基于时间的滑动窗口、基于元组的滑动窗口和分区滑动窗口。
基于时间的滑动窗口(time-based sliding windows):数据流S的基于时间的滑动窗口实质上是大小变化的窗口,窗口以时间T为单位,T为数据流运行时间的计算周期。从直观上来说,基于时间的滑动窗口定义了时间间隔T上的输出关系,从而捕获到有序数据流的最新到达的元组。输出关系可定义为:
R(τ)={S|<S,τ>∈S∧(τ′≤τ)∧(τ′≥max{τ-T,0})}
有两种特殊情况: 当T=0时,R(τ)由数据流S中带有时间戳τ的元素组成;当T=∞时,R(τ)由数据流S中所有时间戮τ≤T的元素组成。
基于元组的滑动窗口(tuple-based windows): 数据流S的基于元组的滑动窗口实质是大小固定的滑动窗口,窗口模型以正整数N作为参数。直观地看,带有时间的基于元组的滑动窗口的输出关系是有序数据流到目前为止最近到达的N个元组。形式上来说,R(τ)是数据流S到目前为止最大时间戳≤τ的N个元组组成。这样就产生一个问题: 假设我们定义了一个N个元组的滑动窗口,在某个时刻,可能有几个第N个最近时间戳的元组,因此要处理这种情况以产生精确的N个元组。如果任意地处理这种情况,基于元组的滑动窗口可能就是非确定的,而且当时间戳不唯一时,基于元组的滑动窗口可能是不合适的。要解决这样的问题,需要引入近似时间戳的概念,使任何两个相邻数据的到达都是在不同的时间间隔内。数据流中计算总和、平均值、直方图、散列表、频率方差等统计值时,采用基于元组的滑动窗口比较方便。
分区滑动窗口(partitioned windows): 数据流上的分区滑动窗口以正整数N和数据流S的属性集{A
1,…,A
t}作为参数。这种窗口将数据流S按属性A
1,…,A
t进行分类(类似于group by),分成各个不同的子数据流,然后对这些子数据流分别得到大小为N、基于元组的滑动窗口。例如,元组s和它的属性值a
1,…,a
t,某时刻的输出关系为R(τ),当且仅当存在一个元素<s,τ′>∈S,τ′≤T,τ′ 是属性值为a
1,…,a
t的N个元素中的最大时间戳。
根据滑动方式不同,滑动窗口分为连续更新滑动窗口和周期更新滑动窗口。连续更新滑动窗口定义为: 设S[t-T:t]为数据流S上的一个滑动窗口,如果t始终保持为S中最新元素到达的时刻,则称S[t-T:t]为连续更新的滑动窗口。
周期更新滑动窗口定义为: 设S[t-T:t]为数据流S的t时刻的一个滑动窗口,△t是一个时间间隔,如果S[t-T:t]仅在每个Δt时间间隔的结束时刻改变为S[t+kΔt-T:t+kΔt],则称S[t-T:t]为周期更新的滑动窗口。
在线咨询
