时间：2022-11-21 14:30:02 | 来源：信息时代
时间：2022-11-21 14:30:02 来源：信息时代
数据流过滤器 : 在数据流中选择满足特定性质的元组。在数据流应用中特别是在多路连接中经常使用过滤器。在连续的元组被处理时,可以形象地将处理流程看成一条管道,对元组的每步操作可看成一个过滤器。每通过一个过滤器,有的元组被过滤,有的元组被保留,最后剩下的元组通过运算得到查询的结果。当然,实际上被保留的元组可能需经过过滤器操作后产生下一个过滤器的输入。过滤器的过滤操作可以是针对元组的投影、选择、连接或者它们的组合构成的运算等。管道式过滤器顺序问题就是在当前环境下,如何安排这些过滤器的顺序而使得处理代价最小,提高处理效率。过滤器在数据流应用中是极为普遍的。
例如,在网络中,A、B、C、D分别为四个路由,需要计算过去半个小时内分别通过四个路由的总的网络流量。本例中有四个流SA、SB、SC和SD,分别表示四个路由产生的数据包,每个数据流的模式相同,都为(pid,size,ts),其中pid为数据包的标记号,size为包的大小,ts为时间戳。每个数据流包含一个基于时间的大小为半个小时的滑动窗口,分别用WA、WB、WC和WD表示,并为pid建立索引以方便查找。当元组t插入WA时,则以一定的顺序检测其他三个窗口WB、WC、WD中pid的索引,即通过过滤器过滤,如果每个窗口中都包含t.pid,则将t送入聚集算子sum(size),否则过滤该元组,不同的顺序导致t被过滤的时刻不同。这里值得指出的是,如果元组t被过滤,则在t被过滤前对t所有的操作都是无效的,也就是说如果t被过滤,则过滤得越早付出的处理代价越小。当元组进入其他窗口时类似。
图1展示了以WD、WB、WC为检测顺序的处理策略。在这种策略下,如果路由A中数据大部分是从路由B和D中来的,而从C中来的很少,则显然没有以WC、WB、WD为检测顺序的处理策略来的高。因为采用WC、WB、WD为检测顺序的处理策略,则许多元组将在第一次检测时被过滤,可以很好地减少处理代价。
输入流滑动窗口
图1 处理策略
在线咨询
