一种基于数据流环境感知的共享过滤算法

发布时间：2018-06-19 08:55

本文选题：多媒体数据流 + 查询　；参考：《计算机研究与发展》2013年05期

【摘要】：为了有效过滤数据流中的有害信息,通常在数据流上注册大量查询,同时构建过滤器来计算这些查询.在多媒体流环境中,查询和过滤器常常是一种"多对多"的连接,也就是说,对于单个过滤器的计算可能会同时给出多个查询的结果.在这种情况下,如何排序所有的过滤器来获得最小的过滤代价变得非常重要.对于过滤器的排序一般依赖于3个指标:过滤器本身的执行代价c、过滤器连接的查询数目p以及过滤器对于随机样本判断为真的概率s.目前基于贪心的排序算法虽然在一定程度上给出了近似最优的结果,但是还存在以下两个问题:1)指标s只是简单依据经验值设定,不能随着流的变化而自适应变化;2)将3个指标融合成一个代价函数进行排序,而没有深入分析各个指标之间的关系.考虑到以上方法存在的不足,提出一个层次排序算法(adaptive hierarchal ordering,AHO)来高效地过滤多媒体数据流.该算法首先依据过滤器的指标c和p进行分类,然后再在每个类别上按照s进行二次排序.在真实多媒体流环境中的过滤结果证明:AHO可以在不降低准确度的情况下,自适应调整过滤器顺序,其性能优于已有的贪心排序算法.
[Abstract]:In order to effectively filter the harmful information in the data stream, a large number of queries are usually registered on the data stream, and a filter is constructed to calculate these queries. In multimedia streaming environment, query and filter are often a kind of "many-to-many" connection, that is, the results of multiple queries may be given for the calculation of a single filter at the same time. In this case, how to sort all filters to get the minimum filter cost becomes very important. The ranking of filters generally depends on three indexes: the execution cost of the filter itself, the number of queries p of the filter join, and the probability of the filter judging to be true for random samples. Although the current greedy sorting algorithm gives an approximate optimal result to a certain extent, there are still two problems, namely, the following two problems: 1) the index s is simply set according to the empirical value. The three indexes can not be adaptively changed with the change of the flow. The three indexes are merged into a cost function to sort without analyzing the relationship between the indexes in depth. Considering the shortcomings of the above methods, a hierarchical sorting algorithm, adaptive hierarchal ordering algorithm (AHOO), is proposed to filter multimedia data streams efficiently. The algorithm first classifies according to the index c and p of the filter, and then reclassifies each category according to s. The filtering results in real multimedia streaming environment show that the proposed scheme can adaptively adjust the order of filters without reducing the accuracy, and its performance is superior to the existing greedy sorting algorithm.
【作者单位】：国网能源研究院;中国科学院信息工程研究所;信息内容安全技术国家工程实验室;
【基金】：国家自然科学基金项目(61003167) 国家“八六三”高技术研究发展计划基金项目(2011AA010705)
【分类号】：TP393.08

【相似文献】